wie man die Komplexität der binären Suche berechnet

144

Ich hörte jemanden sagen, dass die binäre Suche die für die Suche erforderliche Eingabe halbiert und es sich daher um einen log (n) -Algorithmus handelt. Da ich keinen mathematischen Hintergrund habe, kann ich mich nicht darauf beziehen. Kann es jemand etwas genauer erklären? hat es etwas mit der logarithmischen Reihe zu tun?

Häschen
quelle
1
Dies könnte Ihnen helfen: stackoverflow.com/a/13093274/550393
2cupsOfTech

Antworten:

385

Hier eine mathematischere Sichtweise, wenn auch nicht wirklich kompliziert. IMO viel klarer als informelle:

Die Frage ist, wie oft können Sie N durch 2 teilen, bis Sie 1 haben? Dies bedeutet im Wesentlichen, dass Sie eine binäre Suche (die Hälfte der Elemente) durchführen, bis Sie sie gefunden haben. In einer Formel wäre dies:

1 = N / 2 x

mit 2 x multiplizieren :

2 x = N.

Jetzt mache das Protokoll 2 :

log 2 (2 x ) = log 2 N
x * log 2 (2) = log 2 N
x * 1 = log 2 N.

Dies bedeutet, dass Sie log N-mal teilen können, bis Sie alles geteilt haben. Das heißt, Sie müssen log N teilen ("mache den binären Suchschritt"), bis Sie Ihr Element gefunden haben.

duedl0r
quelle
Ich habe es gerade zu t (n) = (2 ^ 2) * K berechnet. Wie mache ich es, um das Formular zu protokollieren?
Shan Khan
1
das gleiche Konzept grafisch erklärt: stackoverflow.com/a/13093274/550393
2cupsOfTech
Der Teil, den ich vermisse, ist, wenn Sie eine BST mit 7 Einträgen haben, wie lautet ihre Formel? log2 (7)? Ich habe mit jedem möglichen Ergebnis eine Brute-Force-Berechnung durchgeführt und bin zu einer Antwort gekommen, die nicht log2 (7) entspricht. Was mache ich also falsch?
Perry Monschau
1
So viel einfacher als die Erklärung des Binärbaums.
NoName
1
Sehr schöne Antwort
VHS
22

Für die binäre Suche ist T (N) = T (N / 2) + O (1) // die Wiederholungsrelation

Anwenden des Mastersatzes zur Berechnung der Laufzeitkomplexität von Wiederholungsrelationen: T (N) = aT (N / b) + f (N)

Hier ist a = 1, b = 2 => log (a Basis b) = 1

auch hier ist f (N) = n ^ c log ^ k (n) // k = 0 & c = log (eine Basis b)

Also ist T (N) = O (N ^ c log ^ (k + 1) N) = O (log (N))

Quelle: http://en.wikipedia.org/wiki/Master_theorem

abstractKarshit
quelle
1
Warum ist log (a base b) 1, wenn a = 1 und b = 2, sollte es nicht 0 sein?
GAURANG VYAS
16

T (n) = T (n / 2) +1

T (n / 2) = T (n / 4) + 1 + 1

Geben Sie den Wert von The (n / 2) oben ein, sodass T (n) = T (n / 4) + 1 + 1 ist. . . . T (n / 2 ^ k) + 1 + 1 + 1 ..... + 1

= T (2 ^ k / 2 ^ k) + 1 + 1 .... + 1 bis k

= T (1) + k

Da haben wir 2 ^ k = n genommen

K = log n

Die zeitliche Komplexität ist also O (log n)

Dhiren Biren
quelle
10

Es ist keine halbe Suchzeit, das würde es nicht protokollieren (n). Es verringert es logarithmisch. Denken Sie einen Moment darüber nach. Wenn Sie 128 Einträge in einer Tabelle hätten und linear nach Ihrem Wert suchen müssten, würden Sie wahrscheinlich durchschnittlich 64 Einträge benötigen, um Ihren Wert zu finden. Das ist n / 2 oder lineare Zeit. Bei einer binären Suche eliminieren Sie die Hälfte der möglichen Einträge bei jeder Iteration, sodass höchstens 7 Vergleiche erforderlich sind, um Ihren Wert zu finden (Protokollbasis 2 von 128 ist 7 oder 2 bis 7 Potenz ist 128.) Dies ist die Kraft der binären Suche.

Michael Dorgan
quelle
Entschuldigung für den Nekropost, aber 128 ist kein gleichmäßig ausgefüllter Baum. Ich habe ein einfaches Beispiel verwendet, um mich damit auseinanderzusetzen, und festgestellt, dass 7 Einträge einen Baum gleichmäßig mit 3 Ebenen füllen. Ich habe berechnet, dass die Komplexität 17/7 (der Mittelwert der Gesamtsumme der Vergleiche) betragen sollte, was 2,43 beträgt. Aber log2 (7) ist 2.81. Was vermisse ich hier?
Perry Monschau
Zwei Antworten - Erste hier: Auch wenn es keinen Fehler in der Mathematik gibt, können wir sehen, dass der Durchschnitt von 2,43 immer noch besser ist als der Durchschnitt von 3,5 für linear, und dies ist ein niedriger Wert. Sobald Sie die Hunderte von Einträgen erreicht haben, ist log2 () viel besser als linear. Ich denke du siehst das aber so weiter.
Michael Dorgan
1
Zweite Antwort: Ich bin mir nicht sicher, welche Art von Baum Sie haben, wo 7 alles ausgefüllt hat. Wenn ich an einen perfekten Baum mit 8 Einträgen denke, sehe ich einen 3-stufigen tiefen Baum mit insgesamt 8 Blättern. Unabhängig davon, nach welcher Zahl Sie suchen, sind in diesem Baum insgesamt 3 Vergleiche erforderlich, um von der Wurzel zum Blatt zu gelangen. Für 7 Einträge würde einer der Pfade einen Vergleich weniger benötigen, also 20/7 (6 Knoten von 3 Vergleichen, 1 Knoten von 2 Vergleichen), was ~ 2,85 ist. Log2 (7) ist ~ 2,81. Ich habe nicht den mathematischen Hintergrund, um den Unterschied von .04 zu erklären, aber ich denke, es hat damit zu tun, dass keine Bruchbits oder andere Magie verfügbar sind :)
Michael Dorgan
Die Anzahl ist die Anzahl der Blätter!? Nicht die Anzahl der Knoten? Nun, das war eine große Information, die mir fehlte. Es scheint mir seltsam, dass die Funktion auf Blättern basiert, wenn jeder Verzweigungsknoten auch ein potenzieller Haltepunkt ist. Na ja, danke, dass du das für mich geklärt hast!
Perry Monschau
5

Die zeitliche Komplexität des binären Suchalgorithmus gehört zur Klasse O (log n). Dies wird als große O-Notation bezeichnet . Sie sollten dies so interpretieren, dass das asymptotische Wachstum der Zeit, die die Funktion für die Ausführung benötigt, bei einem Eingabesatz der Größe n nicht überschritten wird log n.

Dies ist nur eine formale mathematische Umgangssprache, um Aussagen usw. beweisen zu können. Sie hat eine sehr einfache Erklärung. Wenn n sehr groß wird, wächst die log n-Funktion über die Zeit hinaus, die zum Ausführen der Funktion benötigt wird. Die Größe des "Eingabesatzes" n entspricht nur der Länge der Liste.

Einfach ausgedrückt, der Grund für die binäre Suche in O (log n) ist, dass sie die in jeder Iteration festgelegte Eingabe halbiert. In der umgekehrten Situation ist es einfacher, darüber nachzudenken. Wie lange Liste kann der binäre Suchalgorithmus bei x Iterationen bei max untersuchen? Die Antwort ist 2 ^ x. Daraus können wir sehen, dass das Gegenteil der Fall ist, dass der binäre Suchalgorithmus im Durchschnitt log2 n Iterationen für eine Liste der Länge n benötigt.

Wenn es sich um O (log n) und nicht um O (log2 n) handelt, liegt es daran, dass es einfach noch einmal ausgedrückt wird - Die Verwendung der großen O-Notationskonstanten zählt nicht.

vidstige
quelle
4

Hier ist Wikipedia Eintrag

Wenn Sie sich den einfachen iterativen Ansatz ansehen. Sie eliminieren nur die Hälfte der zu durchsuchenden Elemente, bis Sie das gewünschte Element gefunden haben.

Hier ist die Erklärung, wie wir auf die Formel kommen.

Angenommen, Sie haben anfangs N Elemente und dann tun Sie als ersten Versuch „N / 2“. Wobei N die Summe aus Untergrenze und Obergrenze ist. Der erste Zeitwert von N wäre gleich (L + H), wobei L der erste Index (0) und H der letzte Index der Liste ist, nach der Sie suchen. Wenn Sie Glück haben, befindet sich das Element, das Sie suchen, in der Mitte [z. Sie suchen nach 18 in der Liste {16, 17, 18, 19, 20} und berechnen dann ⌊ (0 + 4) / 2⌋ = 2, wobei 0 die Untergrenze ist (L - Index des ersten Elements des Arrays). und 4 ist die höhere Grenze (H - Index des letzten Elements des Arrays). Im obigen Fall ist L = 0 und H = 4. Jetzt ist 2 der Index des Elements 18, das Sie suchen, gefunden. Bingo! Du hast es gefunden.

Wenn der Fall ein anderes Array wäre {15,16,17,18,19}, aber Sie immer noch nach 18 suchen, dann hätten Sie kein Glück und würden zuerst N / 2 machen (das ist ⌊ (0 + 4) / 2⌋ = 2 und stellen Sie dann fest, dass Element 17 am Index 2 nicht die gesuchte Zahl ist. Jetzt wissen Sie, dass Sie bei Ihrem nächsten Versuch, iterativ zu suchen, nicht mindestens die Hälfte des Arrays suchen müssen Der Suchaufwand halbiert sich. Grundsätzlich durchsuchen Sie also nicht jedes Mal die Hälfte der Liste der Elemente, die Sie zuvor gesucht haben, wenn Sie versuchen, das Element zu finden, das Sie bei Ihrem vorherigen Versuch nicht finden konnten.

Der schlimmste Fall wäre also

[N] / 2 + [(N / 2)] / 2 + [((N / 2) / 2)] / 2 .....
dh:
N / 2 1 + N / 2 2 + N / 2 3 + ..... + N / 2 x … ..

bis… Sie mit der Suche fertig sind und sich in dem Element, das Sie suchen, am Ende der Liste befindet.

Dies zeigt, dass der schlimmste Fall ist, wenn Sie N / 2 x erreichen, wobei x so ist, dass 2 x = N ist

In anderen Fällen N / 2 x, wobei x so ist, dass 2 x <N Der Mindestwert von x kann 1 sein, was der beste Fall ist.

Nun, da der mathematisch schlechteste Fall ist, wenn der Wert von
2 x = N
=> log 2 (2 x ) = log 2 (N)
=> x * log 2 (2) = log 2 (N)
=> x * 1 = log 2 (N)
=> Formaler ⌊log 2 (N) + 1⌋

RajKon
quelle
1
Wie genau erhalten Sie die formellere Version?
Kalle
Eine Bodenfunktion wird verwendet. Die Details finden Sie im Abschnitt Leistung des Wiki-Links ( en.wikipedia.org/wiki/Binary_search_algorithm ) in der Antwort.
RajKon
2

Angenommen, die Iteration in der binären Suche endet nach k Iterationen. Bei jeder Iteration wird das Array durch die Hälfte geteilt. Nehmen wir also an, die Länge des Arrays bei jeder Iteration beträgt n. Bei Iteration 1,

Length of array = n

Bei Iteration 2,

Length of array = n⁄2

Bei Iteration 3,

Length of array = (n⁄2)⁄2 = n⁄22

Daher ist nach Iteration k,

Length of array = n⁄2k

Auch wissen wir , dass nach dem Nach k Divisionen, die Länge der Anordnung 1 wird daher

Length of array = n⁄2k = 1
=> n = 2k

Anwenden der Protokollfunktion auf beiden Seiten:

=> log2 (n) = log2 (2k)
=> log2 (n) = k log2 (2)
As (loga (a) = 1)

Deshalb,

As (loga (a) = 1)
k = log2 (n)

Daher ist die zeitliche Komplexität der binären Suche

log2 (n)
SirPhemmiey
quelle
1

Bei einer binären Suche wird das Problem wiederholt in zwei Hälften geteilt (Details weggelassen):

Beispiel für die Suche nach 3 in [4,1,3,8,5]

  1. Bestellen Sie Ihre Artikelliste [1,3,4,5,8]
  2. Schau dir den mittleren Gegenstand an (4),
    • Wenn es das ist, wonach Sie suchen, hören Sie auf
    • Wenn es größer ist, schauen Sie sich die erste Hälfte an
    • Wenn es weniger ist, schauen Sie sich die zweite Hälfte an
  3. Wiederholen Sie Schritt 2 mit der neuen Liste [1, 3], suchen Sie 3 und halten Sie an

Es ist ein bi -nary suchen , wenn Sie das Problem in zwei teilen.

Die Suche erfordert nur log2 (n) Schritte, um den richtigen Wert zu finden.

Ich würde die Einführung in Algorithmen empfehlen , wenn Sie mehr über die algorithmische Komplexität erfahren möchten.

Silas Parker
quelle
1

Da wir eine Liste jedes Mal halbieren, müssen wir nur wissen, in wie vielen Schritten wir 1 erhalten, wenn wir eine Liste durch zwei teilen. In der unten angegebenen Berechnung gibt x an, wie oft wir eine Liste teilen, bis wir ein Element erhalten (im schlimmsten Fall).

1 = N / 2x

2x = N.

Log2 nehmen

log2 (2x) = log2 (N)

x * log2 (2) = log2 (N)

x = log2 (N)

Abdul Malik
quelle
1

T (N) = T (N / 2) + 1

T (N) = T (N / 2) + 1 = (T (N / 4) + 1) + 1

...

T (N) = T (N / N) + (1 + 1 + 1 + ... + 1) = 1 + logN (Basis 2 log) = 1 + logN

Die zeitliche Komplexität der binären Suche ist also O (logN).

TizeeU0U
quelle
0
ok see this
for(i=0;i<n;n=n/2)
{
i++;
}
1. Suppose at i=k the loop terminate. i.e. the loop execute k times.

2. at each iteration n is divided by half.

2.a n=n/2                   .... AT I=1
2.b n=(n/2)/2=n/(2^2)
2.c n=((n/2)/2)/2=n/(2^3)....... aT I=3
2.d n=(((n/2)/2)/2)/2=n/(2^4)

So at i=k , n=1 which is obtain by dividing n  2^k times
n=2^k
1=n/2^k 
k=log(N)  //base 2
Piyush Jain
quelle
0

Lassen Sie mich es Ihnen allen mit einem Beispiel leicht machen.

Nehmen wir der Einfachheit halber an, dass ein Array 32 Elemente in der sortierten Reihenfolge enthält, aus der wir mithilfe der binären Suche nach einem Element suchen.

1 2 3 4 5 6 ... 32

Angenommen, wir suchen nach 32. Nach der ersten Iteration bleiben wir bei

17 18 19 20 .... 32

Nach der zweiten Iteration bleiben wir bei

25 26 27 28 .... 32

Nach der dritten Iteration bleiben wir bei

29 30 31 32

Nach der vierten Iteration bleiben wir bei

31 32

In der fünften Iteration finden wir den Wert 32.

Wenn wir dies in eine mathematische Gleichung umwandeln, erhalten wir

(32 x (1/2 5 )) = 1

=> n X (2- k ) = 1

=> (2 k ) = n

=> k log 2 2 = log 2 n

=> k = log 2 n

Daher der Beweis.

Sumukha HS
quelle
0

Hier ist die Lösung unter Verwendung des Hauptsatzes mit lesbarem LaTeX.

Für jede Wiederholung in der Wiederholungsrelation für die binäre Suche konvertieren wir das Problem in ein Teilproblem mit der Laufzeit T (N / 2). Deshalb:

T (n) = T (n / 2) +1

Wenn wir den Hauptsatz einsetzen, erhalten wir:

T (n) = aT (n / b) + f (n)

Da nun logba0 und f (n) 1 ist, können wir den zweiten Fall des Hauptsatzes verwenden, weil:

f (n) = O (1) = O (n0) = O (nlogba)

Dies bedeutet, dass:

T (n) = O (nlogbalogn) = O (n0logn) = O (logn)

id01
quelle