Die zeitliche Komplexität einer `If` -Aussage ist im Allgemeinen
o (1) , aber mit einigen wichtigen Einschränkungen. Hier ist eine Aufschlüsselung:
Die Kernidee:Konstante Zeit
* Verzweigung ist schnell: Der primäre Betrieb in einer "IF` -Anweisung) bewertet den Zustand und entscheidet, welche Zweigstelle ausgeführt werden soll. Dies ist ein sehr schneller, deterministischer Prozess, der einen einzigen Vergleich beinhaltet (oder einer Reihe von booleschen Operationen, die als begrenzt angesehen werden können). Moderne Prozessoren sind für die bedingte Verzweigung hoch optimiert.
* unabhängig von der Eingangsgröße: Die Entscheidung, den "If` -Block oder den" else "-Block auszuführen (oder auch nicht, wenn es kein" else "gibt), hängt nicht von der Größe der Eingabedaten ab, die vom umgebenden Algorithmus verarbeitet werden. Es hängt nur von der Erkrankung selbst ab.
Warum O (1) irreführend sein kann (Kontext ist wichtig!)
Während die `if` -Anweisung * selbst * o (1) ist, kann der * Code * im Block" If` block oder "else" zu jeder Zeit eine Zeit haben. Das ist entscheidend. Betrachten Sie diese Szenarien:
1. o (1) If-Block:
`` `Python
Wenn x> 5:
y =10 # o (1) Zuweisung
z =x + y # o (1) Zugabe
anders:
y =20 # o (1) Zuordnung
`` `
In diesem Fall sind die "IF` -Anweisung und der Code in * beide * Zweige) o (1). Die Gesamtkomplexität dieses Snippets ist O (1).
2. o (n) If-Block:
`` `Python
Wenn Len (my_list)> 0:
Für mich in Reichweite (len (my_list)):# o (n) Schleife
print (my_list [i])
anders:
print ("Liste ist leer") # O (1)
`` `
Wenn die Bedingung wahr ist, führen Sie eine Schleife aus, die durch `my_list` iteriert, wodurch die Komplexität des" If` -Zweigs O (n)) erstellt wird. Wenn die Bedingung falsch ist, führen Sie O (1) Code aus. Die * schlimmste Fall * Komplexität dieses gesamten Codeblocks ist o (n), da die Anweisung "IF" dazu führen kann, dass der O (N) -Codel ausführt.
3. o (n^2) If-Block:
`` `Python
Wenn Zustand:
für i in Reichweite (n):
für j in Reichweite (n):
# Einige O (1) Operation
passieren
anders:
# O (1) Betrieb
passieren
`` `
In diesem Beispiel wird die zeitliche Komplexität aufgrund der verschachtelten Schleifen innerhalb der `if` -Aussage zu O (n^2), obwohl die Bewertung des" If` -Zustands immer noch o (1) ist.
Zusammenfassend
* Die Verzweigungslogik der `if` -Anweisung ist o (1).
* Die Gesamtzeitkomplexität des Code, der die "IF` -Anweisung" enthält Der Block mit der höchsten Komplexität dominiert.
* Bei der Analyse von Algorithmen müssen Sie das Worst-Case-Szenario berücksichtigen, in dem normalerweise der "If`-Block) mit der höchsten Komplexität ausgeführt wird.
Während Sie sagen können, dass die `if` * -Antage selbst * ständige Zeit nimmt, muss Sie Analysieren Sie den Code in den Zweigen, um die tatsächliche Zeitkomplexität des Codeblocks zu bestimmen, die das "IF`" enthält. Konzentrieren Sie sich auf den dominanten Begriff (den Codeblock, der mit zunehmender Eingabegröße am längsten dauert.
