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

Ўртача ҳол таҳлили
Ўртача ҳол таҳлилини икки босқичга ажратамиз. Дастлаб навбатдаги элементнинг ўрнини аниқлаш учун керак бўлган ўртача солиштиришлар сонини ҳисоблаймиз. Кейин барча керакли амалларни биринчи босқич натижалари орқали ҳисоблаш мумкин. Ишни i- элемент ўрнини аниқлаш учун керак бўлган ўртача солиштиришлар сонини ҳисоблашдан бошлаймиз. Юқорида айтганимиздек i-элементни қўшиш ҳеч бўлмаганда битта солиштиришни талаб қилади.
i – элемент учун нечта мумкин бўлган ўринлар бор? Кичик рўйхатни қарймиз ва натижани ихтиёрий ҳол учун умумийлаштирамиз. Биринчи қўшиладиган элемент учун икки имконият мавжуд: у икки элементли сараланган рўйхатда биринчи ёки иккинчи бўлиши мумкин. Иккинчи қўшиладиган элементда 1, 2 ва 3 рақамли учтадан бир ўрин бор. Демак, i –қўшиладиган элемент учун i+1 дан бир мумкин бўлган ўринлар бор. Бу барча имкониятлар тенг эҳтимолли деб фараз қиламиз.
Ҳар қайси i + 1 мумкин бўлган ўринларга бориш учун нечта солиштириш талаб қилиниди? Яна i нинг кичик қийматларини қараймиз ва натижани умумлаштиришга ҳаракат қиламиз. Агар тўртинчи қўшиладиган элемент 5 ўринга тушса, у ҳолда биринчи солиштириш ёлғон бўлади. Агар тўғри ўрни 4 бўлса, у ҳолда биринчи солиштириш рост иккинчиси эса – ёлғон. 3- ўринга тушишда биринчи ва иккинчи солиштиришлар рост, учинчиси эса– ёлғон. 2- ўринда биринчи, иккинчи ва учинчи солиштиришлар муваффақиятли, тўртинчи эса – йўқ. Биринчи ўринга тушишда биринчи, иккинчи, учинчи ва тўртинчи солиштиришлар рост, ёлғон солиштиришлар бўлмайди. Бу шуни билдирадики, i + 1, i, i- 1, . . . , 2 ўринларга тушувчи i – элемент учун солиштиришлар сони мос равишда 1, 2, 3, ... , i бўлади, биринчи ўринга тушишда солиштиришлар сони i га тенг. i – элементни қўйиш учун солиштиришларнинг ўртача сони қуйидаги тенглик билан берилади

Биз i – элементни қўйишдаги ўртача амаллар сонини ҳисобладик. Энди бу натижаларни N- 1 элементли рўйхат учун йиғиш керак:

(1.11) формулани икки марта қўллаб ҳосил қиламиз

(1.9) ва (1.10) тенгликлардан фойдаланиб қуйидагига эга бўламиз

Энди (1.15), (1.14) ва (1.20) тенгликлар қуйидагини беради