Мундарижа Кириш

Ўртача ҳол таҳлили

Ўртача ҳолни таҳлил қилиш учун ноодатий усулни қўллаймиз. Дастлаб массивдаги қийматлар тескари тартибда жойлашган энг яхши ҳолдан бошлаймиз. Бундай жойлашиш автоматик тўғри пирамидани беришини текшириш қийин эмас. Шу сабабли ҳар бир FixHeap процедуранинг чақирилишида элементлар тўғри жойлашганлигини тасдиқловси икки солиштириш бажарилади. FixHeap процедураси тахминан элементлар ярми учун чақирилади ва ҳар бир чақирув икки солиштириш талаб қилади. Пирамидани қуриш босқичида худди ёмон ҳолдаги каби N солиштириш бажарилади.

Элементларнинг дастлабки жойлашишидан қатъий назар биринчи босқич натижаси доим пирамида бўлади. Шунинг учун исталган ҳолда цикл for ёмон ҳолдаги каби марта бажарилади: Сараланган рўйхатни ҳосил қилиш учун пирамидадан ҳар сафар уни қайта шакллантириб барча элементларни олишимиз керак. шу туфайли энг яхши ҳолда пирамидали саралаш қарийб N + NlogN солиштириш бажаради, яъни энг яхши ҳол қийинлиги га тенг.

Демак, пирамидали саралаш учун энг яхши ва энг ёмон ҳолдаги қийинлик бир хил ва улар га тенг. Бу эса ўртача ҳол қийинлиги ҳам га тенглигини билдиради.