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

Энг яхши ҳол таҳлили
swappedElements нинг нотўғри интерпретациясини огоҳлантириш мақсадида энг яхши ҳолни қисқача қараймиз. Қайси ҳолда бажариладиган иш ҳажми кичик бўлишини қараймиз. Биринчи ўтишда for цикли тўлиқ бажарилиши керак ва шунинг учун алгоритмга энг камида N - 1 солиштириш талаб қилинади. Икки ҳолатни қарашга тўғри келади: биринчи ўтишда ҳеч бўлмаганда битта ўрин алмаштириш ва ўрин алмаштиришлар бўлмаган ҳоллар. Биринчи ҳолда алмаштириш swappedElements қийматини true га ўзгартиради ва демак, while цикли такрорий бажарилади, яъни яна N-2 солиштириш талаб қилади. Иккинчи ҳолда swappedElements мантиқий ифода false қиймат олади ва алгоритм бажарилиши тўхтатилади.
Шу сабабли энг яхши ҳолда N-1 солиштириш бажарилади. Бу шуни кўрсатадики, маълумотларнинг энг яхши тўплами бу – талаб қилинган тартибдаги элементлардан тузилган рўйхатдир.
Энг ёмон ҳол таҳлили
Энг яхши ҳолни талаб қилинган тартибда берилган рўйхат таъминласа, уларнинг тескари ҳолати энг ёмон ҳолни келтириб чиқаради. Бунда биринчи элемент рўйхат охирига қадар ҳар қайси элемент билан солиштирилади. Бу жараён барча қолган элементлар учун такрорланади, шунинг учун for цикли N -1 марта такрорланади. Шу туфайли камайиш тартибидаги рўйхат энг ёмон ҳолатга олиб келади.
Энг ёмон ҳола нечта солиштириш бажарилади? Биринчи ўтишда N - 1 та қўшни қийматлар солиштирилиши бажарилади, иккинчисида – N-2 солиштиришлар. Кейингилари шуни кўрсатадики, ҳар бир навбатдаги ўтишда солиштиришлар сони бирга камаяди. Демак энг ёмон ҳолат қийинлиги қуйидаги формула билан аниқланади

Ўртача ҳол таҳлили
Юқорида айтганимиздек энг ёмон ҳолда for цикли N - 1 марта такрорланади. Ўртача ҳолда исталган бу моментларда алмаштиришларсиз ўтишлар тенг эҳтимолли деб фараз қиламиз. Ҳар бир ҳолда нечта солиштиришлар бажарилишини қараймиз. Биринчи ўтишдан сўнгги тўхташда солиштиришлар сони N – 1 га тенг. Икки ўтишдан сўнг солиштиришлар сони N - 1 + N – 2 га тнг бўлади. C(i) билан биринчи i ўтишда бажарилган солиштиришларни белгилаймиз. Мадомики, агар ҳеч қандай алмаштириш бажарилмаса алгоритм ўз ишини якунлайди ва биз ўртача ҳол таҳлилида бу имкониятларни барчасини қараш керак. Натижада қуйидаги тенгликка келамиз

бунда, С(i) – for циклидаги биринчи i ўтишдаги солиштиришлар сонига тенгва у қуйидагича

(охирги тенглик (1.10) тенгликдан келиб чиқади), ёки



Охирги тенгликни A(N) ифодага қўйиб, ҳосил қиламиз

N– i дан боғлиқ эмас, (1.11) ва (1.14) тенгликлар беради

(1.11) дан яна фойдаланиб ва элементар алгебрани қўллаб қуйидагини ҳосил қиламиз

Ниҳоят, (1.15) ва (1.16) тенгликлар беради