Laiko sudėtingumas apie Dvejetainė paieška yra O(log n) , kur n yra elementų skaičius masyve. Kiekviename žingsnyje jis padalija masyvą per pusę. Erdvės sudėtingumas yra O(1) nes sunaudoja nuolatinį papildomos vietos kiekį.

valstybių sąrašą

Dvejetainės paieškos algoritmo pavyzdys

Dvejetainės paieškos algoritmo laiko ir erdvės sudėtingumas yra nurodytas toliau.

Laiko sudėtingumas Dvejetainės paieškos algoritmas :

Geriausias dvejetainės paieškos algoritmo sudėtingumas: O(1)

Geriausias atvejis yra tada, kai elementas yra viduriniame masyvo indekse. Norint rasti tikslinį elementą, reikia tik vieno palyginimo. Taigi geriausio atvejo sudėtingumas yra O(1) .

Vidutinis dvejetainio paieškos algoritmo atvejo sudėtingumas: O(log N)

Apsvarstykite masyvą arr[] ilgio N ir elementas X būti rastam. Gali būti du atvejai:

10 procentų iš 60

• 1 atvejis: Elementas yra masyve
• 2 atvejis: Elemento masyve nėra.

Yra N 1 atvejis ir 1 2 atvejis. Taigi bendras atvejų skaičius = N+1 . Dabar atkreipkite dėmesį į šiuos dalykus:

• Elementą su indeksu N/2 galima rasti 1 palyginimas
• Rodyklės N/4 ir 3N/4 elementus galima rasti 2 palyginimai.
• Elementus prie indeksų N/8, 3N/8, 5N/8 ir 7N/8 rasite 3 palyginimai ir pan.

Remdamiesi tuo galime daryti išvadą, kad elementai, kuriems reikia:

• 1 palyginimas = 1
• 2 palyginimai = 2
• 3 palyginimai = 4
• x palyginimai = 2 ^x-1 kur x priklauso diapazonui [1, logN] nes maksimalus palyginimas = maksimalus laikas N gali būti sumažintas perpus = maksimalus palyginimas, kad būtų pasiektas 1 elementas = logN.

Taigi, visi palyginimai
= 1*(elementai, kuriems reikia 1 palyginimo) + 2*(elementai, kuriuos reikia palyginti) + . . . + logN* (elementai, kuriuos reikia palyginti logN)
= 1*1 + 2*2 + 3*4 + . . . + logN * (2^logN-1)
= 2^Ramus* (logN – 1) + 1
= N * (logN – 1) + 1

Bendras atvejų skaičius = N+1 .

Todėl vidutinis sudėtingumas = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . Čia dominuojantis terminas yra N*logN/(N+1), kuris yra apytikslis Ramus . Taigi vidutinis bylos sudėtingumas yra O(logN)

Blogiausiu atveju dvejetainio paieškos algoritmo sudėtingumas: O(log N)

Blogiausias atvejis bus tada, kai elementas yra pirmoje padėtyje. Kaip matyti vidutiniu atveju, norint pasiekti pirmąjį elementą reikia palyginti Ramus . Taigi laiko sudėtingumas blogiausiu atveju yra O(logN) .

Dvejetainės paieškos algoritmo pagalbinės erdvės sudėtingumas

The pagalbinės erdvės sudėtingumas iš Dvejetainės paieškos algoritmas yra O(1) , o tai reiškia, kad tam reikia nuolatinio papildomos vietos, nepaisant įvesties masyvo dydžio. Taip yra todėl, kad dvejetainė paieška yra pasikartojantis algoritmas, kuriam nereikia jokių papildomų duomenų struktūrų ar rekursijos, kuri auga didėjant įvesties dydžiui. Nors dvejetainę paiešką galime įdiegti ir rekursyviai.

konvertuojant eilutę į int