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

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

Худди кетма-кет қидириш алгоритмидаги каби таҳлилда икки ҳолатни қараймиз. Биринчиси мақсад қиймат рўйхатда аниқ мавжуд ҳол ва иккинчиси у умуман йўқ ҳолат.

Биринчи ҳолда мақсад қиймат учун мумкин бўлган ҳолатлар N та ва улар тенг эҳтимолли ҳамда уларнинг ҳар бири 1/N га тенг. Агар қидириш жараёнини тавсифловси бинар дарахтни қарайдиган бўлсак, у ҳолда 1 даражада дарахт илдиз элементидан қидириш учун битта солиштириш, иккинчи даражадаги тугунлар элементларидан қидириш учун иккита солиштириш ва учинчи даражада учта солиштириш талаб қилинади. Умуман i даражадаги элементлардан қидириш учун i солиштириш талаб қилинади. 1.3.2 бўлимда кўрсатилганидек, i даражада та тугун мавжуд ва да дарахтда k даража мавжуд. Бу шуки, барча мумкин бўлган ҳоллар учун тўлиқ солиштиришлар сонини ҳар қайси даражадаги солишритиришларни тугунлар сонига кўпаймаларини йиғиндиси ҳисоблаб топиш мумкин. Натижада ўртача ҳол таҳлили қуйидагини беради

(_учун)