Die zeitliche und räumliche Komplexität des Algorithmus

Die Komplexität des Algorithmus bezieht sich auf die Ressourcen, die zum Ausführen des Algorithmus erforderlich sind, nachdem er in ein ausführbares Programm geschrieben wurde. Zu den Ressourcen gehören Zeitressourcen und Speicherressourcen. Anwendungen zur Einführung in Mathematik und Informatik.

Definition der Zeitkomplexität des Algorithmus: (Empfohlenes Lernen: PHP-Video-Tutorial)

In Bearbeitung Während Bei der Algorithmusanalyse ist die Gesamtzahl der Anweisungsausführungen T(n) eine Funktion der Problemgröße n, und dann wird die Änderung von T(n) mit n analysiert und die Größenordnung von T(n) bestimmt. Die Zeitkomplexität des Algorithmus, also die Zeitmessung des Algorithmus, wird wie folgt geschrieben: T(n) = O(f(n)). Dies bedeutet, dass mit zunehmender Problemgröße n die Wachstumsrate der Ausführungszeit des Algorithmus mit der Wachstumsrate von f (n) übereinstimmt, was als asymptotische Zeitkomplexität des Algorithmus bezeichnet wird, die als Zeitkomplexität bezeichnet wird. wobei f(n) eine Funktion der Problemgröße n ist.

Verwenden Sie den Großbuchstaben O(), um die zeitliche Komplexität des Algorithmus widerzuspiegeln, die wir Big-O-Notation nennen.

Wenn in verschiedenen Algorithmen die Anzahl der Anweisungsausführungen im Algorithmus konstant ist, beträgt die Zeitkomplexität O (1). Wenn die Zeithäufigkeit unterschiedlich ist, kann die Zeitkomplexität außerdem gleich sein. Beispielsweise haben T(n)=n^2+3n+4 und T(n)=4n^2+2n+1 unterschiedliche Frequenzen, aber die zeitliche Komplexität ist gleich, beide sind O(n^2).

In aufsteigender Reihenfolge angeordnet sind häufige Zeitkomplexitäten:

Konstante Ordnung O(1), logarithmische Ordnung O(log2n) (Logarithmus von n mit Basis 2, das Gleiche unten) ) , lineare Ordnung O(n),

lineare logarithmische Ordnung O(nlog2n), quadratische Ordnung O(n^2), kubische Ordnung O(n^3),...,

K-te Potenzordnung O(n^k), Exponentialordnung O(2^n). Mit zunehmender Problemgröße n nimmt die oben genannte Zeitkomplexität weiter zu und die Ausführungseffizienz des Algorithmus wird geringer.

Raumkomplexität des Algorithmus

Ähnlich wie die Zeitkomplexität bezieht sich die Raumkomplexität auf die Messung des Speicherplatzes, der erforderlich ist, wenn ein Algorithmus in einem Computer ausgeführt wird.

wird aufgezeichnet als:

S(n)=O(f(n))

Der während der Algorithmusausführung erforderliche Speicherplatz umfasst 3 Teile :

Der vom Algorithmusprogramm belegte Speicherplatz;

Der von den eingegebenen Anfangsdaten belegte Speicherplatz;

Der zusätzliche Speicherplatz, der während der Ausführung des Algorithmus benötigt wird.

Um den vom Algorithmus belegten Speicherplatz zu reduzieren, wird bei vielen praktischen Problemen üblicherweise die Komprimierungsspeichertechnologie verwendet.

Weitere technische Artikel zum Thema PHP finden Sie in der Spalte PHP-Grafik-Tutorial zum Lernen

Das obige ist der detaillierte Inhalt vonDie zeitliche und räumliche Komplexität des Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!