Zeitkomplexität von Binäre Suche Ist O(log n) , Wo N ist die Anzahl der Elemente im Array. Es teilt das Array bei jedem Schritt in zwei Hälften. Raumkomplexität Ist O(1) da es konstant viel zusätzlichen Platz beansprucht.

Holen Sie sich das aktuelle Datum in Java

Beispiel eines binären Suchalgorithmus

Die zeitlichen und räumlichen Komplexitäten des binären Suchalgorithmus werden unten erwähnt.

Zeitkomplexität von Binärer Suchalgorithmus :

Best-Case-Zeitkomplexität des binären Suchalgorithmus: O(1)

Der beste Fall ist, wenn sich das Element am mittleren Index des Arrays befindet. Es ist nur ein Vergleich erforderlich, um das Zielelement zu finden. Die beste Fallkomplexität ist also O(1) .

Durchschnittliche Fallzeitkomplexität des binären Suchalgorithmus: O(log N)

Betrachten Sie ein Array arr[] der Länge N und Element X gefunden werden. Es kann zwei Fälle geben:

• Fall 1: Element ist im Array vorhanden
• Fall2: Das Element ist im Array nicht vorhanden.

Es gibt N Fall1 und 1 Fall2. Also Gesamtzahl der Fälle = N+1 . Beachten Sie nun Folgendes:

Escape-Zeichen Java

• Ein Element mit Index N/2 kann in gefunden werden 1 Vergleich
• Elemente mit Index N/4 und 3N/4 finden sich in 2 Vergleiche.
• Elemente mit den Indizes N/8, 3N/8, 5N/8 und 7N/8 finden sich in 3 Vergleiche usw.

Daraus können wir schließen, dass Elemente, die Folgendes erfordern:

• 1 Vergleich = 1
• 2 Vergleiche = 2
• 3 Vergleiche = 4
• X Vergleiche = 2 ^x-1 Wo X gehört zum Sortiment [1, logN] denn maximale Vergleiche = maximale Zeit N kann halbiert werden = maximale Vergleiche zum Erreichen des 1. Elements = logN.

Also totale Vergleiche
= 1*(Elemente, die 1 Vergleich erfordern) + 2*(Elemente, die 2 Vergleiche erfordern) + . . . + logN*(Elemente, die logN-Vergleiche erfordern)
= 1*1 + 2*2 + 3*4 + . . . + logN * (2^logN-1)
= 2^ruhig* (logN – 1) + 1
= N * (logN – 1) + 1

Gesamtzahl der Fälle = N+1 .

Daher ist die durchschnittliche Komplexität = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . Hier ist der dominierende Term N*logN/(N+1), was ungefähr ist ruhig . Die durchschnittliche Fallkomplexität beträgt also O(logN)

Worst-Case-Zeitkomplexität des binären Suchalgorithmus: O(log N)

Der schlimmste Fall ist, wenn das Element an der ersten Position vorhanden ist. Wie im Durchschnittsfall zu sehen ist, beträgt der zum Erreichen des ersten Elements erforderliche Vergleich ruhig . Die Zeitkomplexität für den schlimmsten Fall beträgt also O(logN) .

Hilfsraumkomplexität des binären Suchalgorithmus

Der Komplexität des Hilfsraums des Binärer Suchalgorithmus Ist O(1) , was bedeutet, dass unabhängig von der Größe des Eingabearrays konstant viel zusätzlicher Speicherplatz benötigt wird. Dies liegt daran, dass es sich bei der binären Suche um einen iterativen Algorithmus handelt, der keine zusätzlichen Datenstrukturen oder Rekursionen erfordert, die mit der Eingabegröße wachsen. Allerdings können wir die binäre Suche auch rekursiv implementieren.

Aufteilen von Zeichenfolgen in C++