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

MergeSort алгоритми таҳлили
MergeLists алгоритми қийинлиги ҳақидаги маълумотларни олгач, энди MergeSort алгоритмига мурожаат қиламиз. Сезиш мумкинки, бу функция ўзгарувчи first қиймати ўзгурувчи last қийматидан кичик ҳолларда рекурсив чақирилаверади. Бу шуни кўрсатадики, агар бу қийматлар тенг ёки first қиймати last дан катта бўлса, рекурсив чақирув бажарилмайди. Агар first ва last тенг бўлса, у ҳолда рўйхат узунлиги бирга тенг, агар first қиймати last дан катта бўлса, у ҳолда нол узунликдаги рўйхатга эга бўламиз. Бу икки ҳолда ҳам алгоритм ҳеч нарса бажармайди ва солиштиришлар сони нолга тенг.
Рўйхатни икки қисмга бўлиш middle қийматини ҳисоблашда рўй беради. Бу ҳисоблаш солиштириш бажармайди ва бўлиш қисмида солиштиришлар нолга тенг. Ўзгарувчи middle нинг қиймати first ва last ўртаси аниқлигида жойлашган, шунинг учун ҳар бир рўйхат узунлиги бутун рўйхат ярмига тенг. N элементдан иборат рўйхатнинг ҳар икки рўйхати N/2 элементлардан тузилган. MergeLsits ал­горитм натижасидан, бирлаштириш босқичида яхши ҳолатда N/2 солиштириш бажарилади, ёмон ҳолда эса солиштиришлар N/2+ N/2 - 1 - N – 1 га тенг. Бу барча катталикларни тўплаб ёмон ҳол учун (W) ва яхши ҳол учун (В) рекуррент муносабатларни ҳосил қиламиз:
W(N) = 2W(N/2)+ N-1,
W(0)= W(1)= 0;
B(N) = 2B(N/2)+ N/2,
B(0) = B(1) = 0.
Энди бу рекуррент муносабатларни § 1.6 бўлим усулларидан фойдаланиб ечамиз. Ёмон ҳолдан бошлаймиз:
W(N/2)= 2W(N/4) + N/2 - 1;
W(N/4)= 2W(N/8) + N/4- 1;
W(N/8) = 2W(N/16)+ N/8 - 1;
W(N/16)= 2W(N/32)+ N/16- 1.
Энди алмаштиришларни бажарамиз:
W(N) = 2W(N/2)+ N - 1
= 2(2W(N/4)+ N/2 - 1) + N - 1
= 4W(N/4) + N - 2 + N-1
= 4(2W(N/8)+ N/4 - 1) + N - 2 + N-1
= 8W(N/8) + N - 4 + N - 2 + N-1
= 8(2W(N/16)+ N/8 -1) +N-4+ N-2 + N-1
= 16W(N/16) +N-8 +N-4 + N-2+N-1
= 16(2W(N/32)+N /16 -1)+N-8+N-4 +N - 2 +N -1
= 32W(N/32) + N - 16 + N-8 + N - 4 + N-2 + N - 1.
Кўриниб турибдики, W олдидаги коэффициент алмашувчи тезлигида ўсади. Охир оқибатда бу аъзо W(1)га тенг бўлади, яъни нолга ва бу қўшилувчи йўқолади. Сезиш мумкинки, ҳар бир алмаштиришда N қўшилувчи қўшилади ва иккининг навбатдаги даражаси айрилади. Натижа қандай бўлади? Охирги тенгликнинг ўнг қисмида 5 та N қўшилувчи ва икки даражалари йиғиндиси нолдан (1 = 2°) то тўртгача (16=2⁴), яна W(N/32)=W(N/2⁵). Шунинг учун охирги тенгликка етганимизда тенглик қуйидаги ёпиқ шаклга эга бўлади:

Бу шуни билдирадики, W(N) = O(N log N). W(N)дан B(N)га ўтиш фарқи шуки, N ни N/2 билан алмаштирилади. N нинг алмаштиришлардаги аҳамиятини ўрганиб, ҳосил қилиш мумкинки , шу туфайли энг яхши ҳол учун ҳам B(N)=(N log N) ўринли.
Бу шуни кўрсатадики, бирлаштириб саралаш ҳатто энг ёмон ҳолда ҳам жуда самарадор, аммо бирлаштириш процедураси MergeLists учун қўшимча хотира талаб қилинади.