Tidskompleksitet av Binært søk er O(log n) , hvor n er antall elementer i matrisen. Den deler matrisen i to ved hvert trinn. Romkompleksitet er O(1) da den bruker en konstant mengde ekstra plass.

java objektlikhet

Eksempel på binær søkealgoritme

Tids- og romkompleksiteten til den binære søkealgoritmen er nevnt nedenfor.

Tidskompleksiteten til Binær søkealgoritme :

Beste case-tidskompleksitet for binær søkealgoritme: O(1)

Beste tilfelle er når elementet er i den midterste indeksen av matrisen. Det tar bare én sammenligning for å finne målelementet. Så den beste sakskompleksiteten er O(1) .

Gjennomsnittlig sakstidskompleksitet for binær søkealgoritme: O(log N)

Vurder array arr[] av lengde N og element X å bli funnet. Det kan være to tilfeller:

• Sak 1: Element er tilstede i matrisen
• Sak 2: Elementet er ikke til stede i matrisen.

Det er N Sak 1 og 1 Sak 2. Så totalt antall tilfeller = N+1 . Legg nå merke til følgende:

• Et element ved indeks N/2 finnes i 1 sammenligning
• Elementer ved indeks N/4 og 3N/4 finnes i 2 sammenligninger.
• Elementer ved indeksene N/8, 3N/8, 5N/8 og 7N/8 finnes i 3 sammenligninger og så videre.

Basert på dette kan vi konkludere med at elementer som krever:

få matriselengde i c

• 1 sammenligning = 1
• 2 sammenligninger = 2
• 3 sammenligninger = 4
• x sammenligninger = 2 ^x-1 hvor x tilhører sortimentet [1, logN] fordi maksimale sammenligninger = maksimal tid N kan halveres = maksimale sammenligninger for å nå 1. element = logN.

Så totalt sammenligninger
= 1*(elementer som krever 1 sammenligninger) + 2*(elementer som krever 2 sammenligninger) + . . . + logN*(elementer som krever logN-sammenligninger)
= 1*1 + 2*2 + 3*4 + . . . + logN * (2^logN-1)
= 2^rolig* (logN – 1) + 1
= N * (logN – 1) + 1

Totalt antall tilfeller = N+1 .

Derfor er gjennomsnittlig kompleksitet = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . Her er det dominerende leddet N*logN/(N+1) som er omtrentlig rolig . Så den gjennomsnittlige sakskompleksiteten er O(logN)

slett filen i java

Worst Case Tidskompleksitet av binær søkealgoritme: O(log N)

Det verste tilfellet vil være når elementet er tilstede i første posisjon. Som sett i det gjennomsnittlige tilfellet, er sammenligningen som kreves for å nå det første elementet rolig . Så tidskompleksiteten for verste fall er O(logN) .

Auxiliary Space Complexity of Binary Search Algoritme

De hjelperoms kompleksitet av Binær søkealgoritme er O(1) , noe som betyr at den krever en konstant mengde ekstra plass uavhengig av størrelsen på inngangsmatrisen. Dette er fordi binært søk er en iterativ algoritme som ikke krever noen ekstra datastrukturer eller rekursjon som vokser med inndatastørrelsen. Selv om vi også kan implementere binært søk rekursivt.