Časová složitost z Binární vyhledávání je O(log n) , kde n je počet prvků v poli. V každém kroku rozdělí pole na polovinu. Prostorová složitost je O(1) protože využívá konstantní množství prostoru navíc.

zřetězit java řetězec

Příklad binárního vyhledávacího algoritmu

Časová a prostorová složitost binárního vyhledávacího algoritmu je uvedena níže.

Časová složitost Binární vyhledávací algoritmus :

Časová složitost nejlepšího případu binárního vyhledávacího algoritmu: O(1)

Nejlepší případ je, když je prvek na středním indexu pole. K nalezení cílového prvku je potřeba pouze jedno srovnání. Nejlepší je tedy složitost případu O(1) .

Průměrná časová složitost binárního vyhledávacího algoritmu: O(log N)

Zvažte pole arr[] délky N a prvek X být nalezen. Mohou nastat dva případy:

• Případ 1: Prvek je přítomen v poli
• Případ 2: Prvek není v poli přítomen.

Existují N Případ1 a 1 Případ2. Takže celkový počet případů = N+1 . Nyní si všimněte následujícího:

• Prvek na indexu N/2 lze nalézt v 1 srovnání
• Prvky na indexu N/4 a 3N/4 lze nalézt v 2 srovnání.
• Prvky u indexů N/8, 3N/8, 5N/8 a 7N/8 lze nalézt v 3 srovnání a tak dále.

Na základě toho můžeme dojít k závěru, že prvky, které vyžadují:

• 1 srovnání = 1
• 2 srovnání = 2
• 3 srovnání = 4
• X srovnání = 2 ^x-1 kde X patří do sortimentu [1, logN] protože maximální srovnání = maximální čas N lze zkrátit na polovinu = maximální srovnání k dosažení 1. prvku = logN.

Takže totální srovnání
= 1*(prvky vyžadující 1 srovnání) + 2*(prvky vyžadující 2 srovnání) + . . . + logN* (prvky vyžadující porovnání logN)
= 1*1 + 2*2 + 3*4 +. . . + logN * (2^logN-1)
= 2^uklidnit* (logN – 1) + 1
= N * (logN – 1) + 1

tisknout vzor hvězdy

Celkový počet případů = N+1 .

q2 měsíce

Proto průměrná složitost = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . Zde je dominantním členem N*logN/(N+1), což je přibližně uklidnit . Průměrná složitost případu je tedy taková O(logN)

Nejhorší případ časová složitost binárního vyhledávacího algoritmu: O(log N)

Nejhorší případ bude, když je prvek přítomen na první pozici. Jak je vidět v průměrném případě, srovnání potřebné k dosažení prvního prvku je uklidnit . Časová náročnost pro nejhorší případ tedy je O(logN) .

Složitost pomocného prostoru binárního vyhledávacího algoritmu

The složitost pomocného prostoru z Binární vyhledávací algoritmus je O(1) , což znamená, že vyžaduje konstantní množství místa navíc bez ohledu na velikost vstupního pole. Je to proto, že Binary Search je iterativní algoritmus, který nevyžaduje žádné další datové struktury nebo rekurzi, která roste s velikostí vstupu. I když můžeme také implementovat binární vyhledávání rekurzivně.