In der Informatik wird Zeitkomplexität, auch Zeitkomplexität genannt, Grad, der Zeitkomplexität eines Algorithmus ist eine Funktion, die die Laufzeit des Algorithmus qualitativ beschreibt. Dies ist eine Funktion der Länge der Zeichenfolge, die den Eingabewert für den Algorithmus darstellt. Zeitkomplexität wird oft in der großen O-Notation ausgedrückt, wobei die Terme niedriger Ordnung und führende Koeffizienten dieser Funktion ausgeschlossen sind. Bei Verwendung dieses Ansatzes kann man sagen, dass die Zeitkomplexität asymptotisch ist, d. h. wenn sich die Größe der Eingabewerte der Unendlichkeit nähert.
Um die Zeitkomplexität zu berechnen, schätzen wir normalerweise die Anzahl der Operationseinheiten des Algorithmus, und die Laufzeit jeder Einheit ist gleich. Daher unterscheiden sich die Gesamtlaufzeit und die Anzahl der Betriebseinheiten des Algorithmus höchstens um einen konstanten Faktor.
Unterschiedliche Eingabewerte gleicher Größe können immer noch dazu führen, dass die Laufzeit des Algorithmus unterschiedlich ist. Daher verwenden wir normalerweise die Worst-Case-Komplexität des Algorithmus, die als T (n) bezeichnet wird Definiert als die Zeit, die für Eingaben beliebiger Größe erforderlich ist. Maximale Laufzeit. Eine andere, weniger häufig verwendete Methode ist die durchschnittliche Fallkomplexität, die normalerweise nur verwendet wird, wenn sie spezifiziert ist. Die Zeitkomplexität kann anhand der natürlichen Eigenschaften der Funktion T(n) klassifiziert werden. Beispielsweise wird ein Algorithmus mit T(n) =O(n) als „linearer Zeitalgorithmus“ bezeichnet; ^n) und M= O(T(n)), der Algorithmus mit M≥n> wird als „exponentieller Zeitalgorithmus“ bezeichnet.
Die Zeit, die ein Algorithmus benötigt, ist proportional zur Anzahl der Ausführungen von Anweisungen im Algorithmus. Je nachdem, welcher Algorithmus mehr Anweisungen hat, benötigt er mehr Zeit. Die Anzahl der Anweisungsausführungen in einem Algorithmus wird als Anweisungshäufigkeit oder Zeithäufigkeit bezeichnet. Bezeichnen Sie es als T(n).
Im Allgemeinen ist die Anzahl der wiederholten Ausführungen grundlegender Operationen in einem Algorithmus eine Funktion der Problemgröße n, dargestellt durch T(n). Wenn es eine Hilfsfunktion f(n) gibt, nähert sich n der Unendlichkeit Ist der Grenzwert von T(n)/f(n) eine Konstante ungleich Null, dann heißt f(n) eine Funktion in der gleichen Größenordnung wie T(n). Mit der Bezeichnung T(n)=O(f(n)) wird O(f(n)) als asymptotische Zeitkomplexität des Algorithmus oder kurz Zeitkomplexität bezeichnet.
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, z. B. T (n)=n2+3n+4 und T(n)=4n2+2n+1 haben unterschiedliche Frequenzen, aber die zeitliche Komplexität ist gleich, beide sind O(n2).
Zeithäufigkeit
Die Zeit, die zur Ausführung eines Algorithmus benötigt wird, kann nicht theoretisch berechnet werden. Sie kann nur durch die Ausführung eines Tests am Computer ermittelt werden. Aber es ist für uns unmöglich und unnötig, jeden Algorithmus auf dem Computer zu testen. Wir müssen nur wissen, welcher Algorithmus mehr Zeit benötigt und welcher weniger Zeit benötigt. Und die Zeit, die ein Algorithmus benötigt, ist proportional zur Anzahl der Ausführungen von Anweisungen im Algorithmus. Je nachdem, welcher Algorithmus mehr Anweisungen hat, benötigt er mehr Zeit. Die Anzahl der Anweisungsausführungen in einem Algorithmus wird als Anweisungshäufigkeit oder Zeithäufigkeit bezeichnet. Bezeichnen Sie es als T(n).
Ähnlich wie Zeitkomplexität bezieht sich Raumkomplexität auf die Messung des Speicherplatzes, der benötigt wird, wenn ein Algorithmus in einem Computer ausgeführt wird. Aufgezeichnet als:
S(n)=O(f(n))
Der während der Algorithmusausführung erforderliche Speicherplatz besteht aus 3 Teilen:
Der vom Algorithmusprogramm belegte Speicherplatz; Raum.
Um den vom Algorithmus belegten Speicherplatz zu reduzieren, wird bei vielen praktischen Problemen üblicherweise die Komprimierungsspeichertechnologie verwendet.
Das obige ist der detaillierte Inhalt vonWas beinhaltet die Algorithmuskomplexität hauptsächlich?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
