Časová zložitosť z Binárne vyhľadávanie je O (log n) , kde n je počet prvkov v poli. V každom kroku rozdelí pole na polovicu. Priestorová zložitosť je O(1) pretože využíva konštantné množstvo priestoru navyše.

formátovať dátum na reťazec

Príklad binárneho vyhľadávacieho algoritmu

Časová a priestorová zložitosť binárneho vyhľadávacieho algoritmu je uvedená nižšie.

Časová zložitosť Binárny vyhľadávací algoritmus :

Časová zložitosť najlepšieho prípadu binárneho vyhľadávacieho algoritmu: O(1)

Najlepší prípad je, keď je prvok na strednom indexe poľa. Na nájdenie cieľového prvku je potrebné iba jedno porovnanie. Takže najlepšia zložitosť prípadu je O(1) .

Priemerná časová zložitosť binárneho vyhľadávacieho algoritmu: O (log N)

Zvážte pole arr[] dĺžky N a prvok X byť nájdený. Môžu nastať dva prípady:

• Prípad 1: Prvok je prítomný v poli
• Prípad 2: Prvok nie je prítomný v poli.

Existujú N Prípad 1 a 1 Prípad2. Takže celkový počet prípadov = N+1 . Teraz si všimnite nasledovné:

• Prvok na indexe N/2 možno nájsť v 1 porovnanie
• Prvky s indexom N/4 a 3N/4 možno nájsť v 2 prirovnania.
• Prvky pri indexoch N/8, 3N/8, 5N/8 a 7N/8 nájdete v 3 porovnania a pod.

Na základe toho môžeme konštatovať, že prvky, ktoré vyžadujú:

urobiť while slučku v jave

• 1 porovnanie = 1
• 2 porovnania = 2
• 3 porovnania = 4
• X prirovnania = 2 ^x-1 kde X patrí do sortimentu [1, logN] pretože maximálne porovnania = maximálny čas N možno znížiť na polovicu = maximálne porovnania na dosiahnutie 1. prvku = logN.

Takže totálne porovnania
= 1*(prvky vyžadujúce 1 porovnanie) + 2*(prvky vyžadujúce 2 porovnania) + . . . + logN* (prvky vyžadujúce porovnanie logN)
= 1*1 + 2*2 + 3*4 +. . . + logN * (2^logN-1)
= 2^pokojne* (logN – 1) + 1
= N* (logN – 1) + 1

Celkový počet prípadov = N+1 .

Preto priemerná zložitosť = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . Tu je dominantný člen N*logN/(N+1), čo je približne pokojne . Priemerná zložitosť prípadu je teda O(logN)

ktorý vytvoril školu

Časová zložitosť binárneho vyhľadávacieho algoritmu v najhoršom prípade: O (log N)

Najhorší prípad bude, keď bude prvok prítomný na prvej pozícii. Ako je vidieť v priemernom prípade, porovnanie potrebné na dosiahnutie prvého prvku je pokojne . Takže časová náročnosť pre najhorší prípad je O(logN) .

Zložitosť pomocného priestoru binárneho vyhľadávacieho algoritmu

The zložitosť pomocného priestoru z Binárny vyhľadávací algoritmus je O(1) , čo znamená, že vyžaduje konštantné množstvo priestoru navyše bez ohľadu na veľkosť vstupného poľa. Je to preto, že Binary Search je iteratívny algoritmus, ktorý nevyžaduje žiadne ďalšie dátové štruktúry ani rekurziu, ktorá rastie s veľkosťou vstupu. Binárne vyhľadávanie však môžeme implementovať aj rekurzívne.