Wie hoch ist die zeitliche Komplexität eines Programms, das den binären Suchalgorithmus verwendet?

Die zeitliche Komplexität eines Programms, das den binären Suchalgorithmus verwendet, liegt auf der „logarithmischen Ebene“. Die binäre Suche ist eine hocheffiziente Suchmethode. Die Komplexität des Algorithmus ist die Anzahl der While-Schleifen. Die Zeitkomplexität kann als „O(h)=O(log2n)“ ausgedrückt werden.

Die Betriebsumgebung dieses Tutorials: Windows 7-System, Dell G3-Computer.

Die zeitliche Komplexität eines Programms, das den binären Suchalgorithmus verwendet, liegt auf der „logarithmischen Ebene“.

Verwandte Empfehlungen: „Programmieren lernen“

Die binäre Suche wird auch als binäre Suche (Binary Search) bezeichnet und ist eine effizientere Suchmethode. Die binäre Suche erfordert jedoch, dass die lineare Tabelle eine sequentielle Speicherstruktur annimmt und die Elemente in der Tabelle nach Schlüsselwörtern geordnet werden müssen.

Suchvorgang:

Angenommen, die Elemente in der Tabelle sind in aufsteigender Reihenfolge angeordnet, vergleichen Sie die in der Mitte der Tabelle aufgezeichneten Schlüsselwörter mit den Suchschlüsselwörtern. Wenn die beiden gleich sind, ist die Suche erfolgreich. Andernfalls verwenden Sie die Datensätze in der Mitte, um die Tabelle zu verschieben. Sie ist in zwei Untertabellen unterteilt, die vordere und die hintere. Wenn das in der mittleren Position aufgezeichnete Schlüsselwort größer als das Suchschlüsselwort ist, wird die vorherige Untertabelle durchsucht weiter, andernfalls wird die letztgenannte Untertabelle weiter durchsucht. Wiederholen Sie den obigen Vorgang, bis ein Datensatz gefunden wird, der die Bedingungen erfüllt, wodurch die Suche erfolgreich ist, oder bis die Untertabelle nicht mehr vorhanden ist. In diesem Fall schlägt die Suche fehl.

Algorithmuskomplexität:

Die Grundidee der binären Suche besteht darin, n Elemente in zwei ungefähr gleiche Teile zu teilen und a[n/2] mit x zu vergleichen Wenn x gefunden wird, wird der Algorithmus beendet, wenn .

Die Zeitkomplexität die Anzahl der While-Schleifen ist.

Es gibt insgesamt n Elemente,

folgt nach und nach n, n/2, n/4, .... n/2^k (die verbleibende Anzahl der Elemente, die als nächstes bearbeitet werden sollen), wobei k die Zahl ist von Schleifen

Da Ihr n/2^k gerundet ist >=1

Das heißt, wenn n/2^k=1

, können Sie k=log2n erhalten (was der Logarithmus von n zur Basis 2 ist)

so die Zeit Die Komplexität kann ausgedrückt werden als O(h)=O(log2n)

Das Folgende ist ein Pseudocode für die Implementierung der binären Suche:

BinarySearch(max,min,des)
mid-<(max+min)/2
while(min<=max)
mid=(min+max)/2
if mid=des then
return mid
elseif mid >des then
max=mid-1
else
min=mid+1
return max

Die Halbsuchmethode wird auch als binäre Suchmethode bezeichnet. Sie nutzt die Ordnungsbeziehung zwischen Elementen vollständig aus und übernimmt die Divide-and-Conquer-Strategie. Im schlimmsten Fall kann die Suchaufgabe in O(log n) abgeschlossen werden. Seine Grundidee ist: (unter der Annahme, dass die Array-Elemente in aufsteigender Reihenfolge angeordnet sind) n Elemente in zwei Hälften mit ungefähr der gleichen Anzahl teilen, a[n/2] nehmen und es mit dem x vergleichen, das Sie finden möchten, wenn x= a[n/ 2] dann wird x gefunden und der Algorithmus endet; wenn x

Weitere verwandte Artikel finden Sie auf der Chinesischen PHP-Website! !

Das obige ist der detaillierte Inhalt vonWie hoch ist die zeitliche Komplexität eines Programms, das den binären Suchalgorithmus verwendet?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!