Erklären Sie die Zeit Komplexität des Algorithmus

Question

while(low <= high) 
{ 
    mid = (low + high)/2; 
    if (target < list[mid]) 
    high = mid - 1; 
    else if (target > list[mid]) 
    low = mid + 1; 
    else break; 
} 

Dies ist Binär-Suche natürlich, aber ich möchte die Komplexität finden.

Nur vom Code zu sehen, wie würde ich das Big-O finden?

Für die while Schleife wird es im Durchschnitt laufen N/2 mal richtig?

Aber wenn du nicht wüsstest, dass das binäre Suche war, wie würdest du das Big-O dieses Codes finden, wenn du dir den Code anschaust?

Answer 1

Sie müssen nur sehen, wie die while() Zustand ändern ...

low <= high bedeutet, dass Sie sehen müssen, wie high - low verhalten.

und aus dem Code, finden Sie, was es am wenigsten ändert! (Worst case)
hier wird es durch den Faktor 2 verringert (entweder niedrig Voraus um die Hälfte, oder umgekehrt)

dann:
T (x < = 0) = 1;
T (N) = T (N/2)

Answer 2

Da Big-O-Notation mit Worst-Case-Komplexität betrifft, brauchen wir nur die Worst-Case-Szenario dieses Codes zu kümmern, was bedeutet, wenn die break Linie wird nie erreicht.

Die anderen Zweige if bedeuten nach jeder Iteration der Schleife while, der Abstand von low zu high etwa in der Hälfte reduziert wird.

Angenommen N=|high-low| zunächst, dann d schließlich zu N/2, N/4, ... N/(2^n) während 2^n größer oder gleich d so dass das Verhältnis N/(2^n) gleich zu 0. Das heißt, wenn die high < low und while Schleife beendet.

Also, wie oft können wir teilen N von 2 teilen? Die Antwort ist ungefähr der Logarithmus von N in der Basis 2, daher die log(N) Komplexität.