Laika sarežģītība no Binārā meklēšana ir O(log n) , kur n ir elementu skaits masīvā. Tas sadala masīvu uz pusēm katrā solī. Telpas sarežģītība ir O(1) jo tas izmanto nemainīgu papildu vietas daudzumu.

attiecību sastāvs

Binārās meklēšanas algoritma piemērs

Binārās meklēšanas algoritma sarežģītība laikā un telpā ir minēta zemāk.

Laika sarežģītība Binārās meklēšanas algoritms :

Binārās meklēšanas algoritma sarežģītība vislabākajā gadījumā: O(1)

Labākais gadījums ir tad, ja elements atrodas masīva vidējā rādītājā. Lai atrastu mērķa elementu, ir nepieciešams tikai viens salīdzinājums. Tātad labākā gadījuma sarežģītība ir O(1) .

Binārās meklēšanas algoritma vidējā gadījuma laika sarežģītība: O(log N)

Apsveriet masīvu arr[] garuma N un elements X jāatrod. Var būt divi gadījumi:

• 1. gadījums: Elements atrodas masīvā
• 2. gadījums: Elements masīvā nav.

Tur ir N 1. gadījums un 1 2. gadījums. Tātad kopējais lietu skaits = N+1 . Tagad ievērojiet sekojošo:

• Elementu ar indeksu N/2 var atrast 1 salīdzinājums
• Elementus ar indeksu N/4 un 3N/4 var atrast 2 salīdzinājumiem.
• Elementus indeksos N/8, 3N/8, 5N/8 un 7N/8 var atrast 3 salīdzinājumi un tā tālāk.

Pamatojoties uz to, mēs varam secināt, ka elementi, kuriem nepieciešami:

• 1 salīdzinājums = 1
• 2 salīdzinājumi = 2
• 3 salīdzinājumi = 4
• x salīdzinājumi = 2 ^x-1 kur x pieder diapazonam [1, logN] jo maksimālie salīdzinājumi = maksimālais laiks N var tikt samazināts uz pusi = maksimālais salīdzinājums, lai sasniegtu 1. elementu = logN.

Tātad, kopējie salīdzinājumi
= 1*(elementi, kuriem nepieciešams 1 salīdzinājums) + 2*(elementi, kuriem nepieciešams 2 salīdzinājums) + . . . + logN* (elementi, kuriem nepieciešams logN salīdzinājums)
= 1*1 + 2*2 + 3*4 + . . . + logN * (2^logN-1)
= 2^mierīgs* (logN – 1) + 1
= N * (logN – 1) + 1

formāta virkne java

Kopējais lietu skaits = N+1 .

kolekcijas java

Tāpēc vidējā sarežģītība = ( N*(logN – 1) + 1)/N+1 = N*logN/(N+1)+1/(N+1) . Šeit dominējošais termins ir N*logN/(N+1), kas ir aptuveni mierīgs . Tātad vidējā lietas sarežģītība ir O(logN)

Binārās meklēšanas algoritma sarežģītība sliktākajā gadījumā: O(log N)

Sliktākais gadījums būs tad, kad elements atrodas pirmajā pozīcijā. Kā redzams vidējā gadījumā, salīdzinājums, kas nepieciešams, lai sasniegtu pirmo elementu, ir mierīgs . Tātad laika sarežģītība sliktākajā gadījumā ir O(logN) .

Binārās meklēšanas algoritma palīgtelpas sarežģītība

The palīgtelpas sarežģītība no Binārās meklēšanas algoritms ir O(1) , kas nozīmē, ka neatkarīgi no ievades masīva lieluma ir nepieciešams pastāvīgs papildu vietas daudzums. Tas ir tāpēc, ka binārā meklēšana ir iteratīvs algoritms, kam nav nepieciešamas nekādas papildu datu struktūras vai rekursija, kas pieaug līdz ar ievades lielumu. Lai gan mēs varam arī ieviest bināro meklēšanu rekursīvi.