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

Бўлакларни қуришдаги солиштиришлар сони

Биз сараланган бўлакларни қуришда ишлатиладиган алгоритмни аниқладик. Фараз қилайлик ишлатилган саралаш қийинлиги O(NlogN) га тенг бўлсин. Мадомики бўлак узунлиги 5 га тенг, ҳар қайси бўлак О(5 log 5) амаллар талаб қилади. Бўлакларнинг умумий сони R га тенг, шунинг учун барча бўлакларни саралаш учун O(RS log 5) = O(N log S) солиштиришлар талаб этилади. Шундай қилиб, бўлакларни қуриш босқичи O(NlogS)га тенг.

Бўлакларни бирлаштиришдаги солиштиришлар сони

Юқорида кўрсатганимиздек А ва В элементлардан иборат икки рўйхатни MergeLists алгоритми билан бирлаштиришда энг ёмон ҳолда А+В–1 солиштиришлар талаб қилинади. Бизнинг ҳолда биринчи ўтишда S узунликдаги R бўлаклар бирлаштирилади, яъни жами R/2 бирлаштириш юз беради ва ҳар бир бирлаштириш 25 – 1 кам солиштириш талаб қилади. Демак биринчи ўтишдаги солиштиришларнинг умумий сони R/1 • (25 – 1) = RS – R/2 дан ошмайди. Иккинчи ўтишда биз ҳарбири узунлиги 25 бўлган R/2 бўлаклар билан иш кўрамиз, шунинг учун жами R /4 бирлаштириш талаб этилади, ҳар бири учун 2(25) – 1 кам солиштиришлар талаб этилади, яъни солиштиришларнинг умумий сони R /4 • (45 – 1) = RS – R/4 дан ошмайди. Учинчи ўтишда биз узунлиги 45 дан бўлган R/4 бўлакларни бирлаштирамиз ва бу R/8 бирлаштиришдан ҳар бири 2(45) – 1 дан кам солиштириш талаб қилади, шунинг учун солиштиришларнинг умумий сони R/8 • (85 - 1) = RS – R/8 катталик билан баҳоланади.

Энди агар бирлаштириш алгоритмидаги ўтишлар сони га тенглигини эсласак, уҳолда бирлаштириш босқичидаги умумий солиштиришлар сонини ҳисоблаш мумкин:



Иккинчи тенгликда 1/2 + 1/4 + 1/8 +… йиғинди ҳар доим 1 дан кам сонга тенг бўлишидан фойдаландик, аммо у ҳеч қачон 1 га ета олмайди. Яна (1.18) тенгликдан А – 0.5 да фойдаланиш мумкин (бунда i = 0 дан бошланади).

Демак, бўлакларни бирлаштириш босқичи қийинлиги O(Nlog R) га тенг. Шунинг учун алгоритмнинг бутун қийинлиги қуйидагича

O(N log S+ N log R) = O[N(log S + log R)]

= O[Nlog(RS)] ((1.5)тенгликдан)

= O[Nlog(S·N/S)]

= O(NlogN).