Tidskompleksitet af Binær søgning er O(log n) , hvor n er antallet af elementer i arrayet. Den deler arrayet i to ved hvert trin. Rumkompleksitet er O(1) da det bruger en konstant mængde ekstra plads.

intelligent idé vs formørkelse

Eksempel på binær søgealgoritme

Tids- og rumkompleksiteten af ​​den binære søgealgoritme er nævnt nedenfor.

Tidskompleksitet af Binær søgealgoritme :

Bedste tilfælde tidskompleksitet af binær søgealgoritme: O(1)

Bedste tilfælde er, når elementet er i det midterste indeks af arrayet. Det kræver kun én sammenligning at finde målelementet. Så den bedste sags kompleksitet er O(1) .

Gennemsnitlig sagstidskompleksitet af binær søgealgoritme: O(log N)

Overvej array arr[] af længde N og element x at blive fundet. Der kan være to tilfælde:

• Sag 1: Element er til stede i arrayet
• Sag 2: Element er ikke til stede i arrayet.

Der er N Case 1 og 1 Sag 2. Så det samlede antal tilfælde = N+1 . Bemærk nu følgende:

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

Baseret på dette kan vi konkludere, at elementer, der kræver:

få array længde i c

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

Altså samlede sammenligninger
= 1*(elementer, der kræver 1 sammenligninger) + 2*(elementer, der kræver 2 sammenligninger) + . . . + logN*(elementer, der kræver logN-sammenligninger)
= 1*1 + 2*2 + 3*4 +. . . + logN * (2^logN-1)
= 2^berolige* (logN – 1) + 1
= N * (logN – 1) + 1

Samlet antal tilfælde = N+1 .

Derfor er den gennemsnitlige kompleksitet = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . Her er det dominerende led N*logN/(N+1), hvilket er ca berolige . Så den gennemsnitlige sagskompleksitet er O(logN)

bibliotek omdøb linux

Worst case tidskompleksitet af binær søgealgoritme: O(log N)

Det værste tilfælde vil være, når elementet er til stede i den første position. Som det ses i det gennemsnitlige tilfælde, er den sammenligning, der kræves for at nå det første element berolige . Så tidskompleksiteten for worst case er O(logN) .

Auxiliary Space Complexity of Binary Search Algoritme

Det hjælperums kompleksitet af Binær søgealgoritme er O(1) , hvilket betyder, at det kræver en konstant mængde ekstra plads uanset størrelsen på input-arrayet. Dette skyldes, at binær søgning er en iterativ algoritme, der ikke kræver yderligere datastrukturer eller rekursion, der vokser med inputstørrelsen. Selvom vi også kan implementere binær søgning rekursivt.