Wie misst man die Ausführungszeiteffizienz eines Algorithmus?

Auf der Grundlage der Ignorierung der Maschinenleistung verwenden wir die Zeitkomplexität des Algorithmus, um die Ausführungszeit des Algorithmus zu messen.
1. Zeithäufigkeit
Die Zeit, die zur Ausführung eines Algorithmus benötigt wird, kann nicht theoretisch berechnet werden. Sie müssen einen Test auf einem Computer durchführen, um dies zu ermitteln. 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. UndDie 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).
2. Zeitkomplexität
In der gerade erwähnten Zeitfrequenz wird n als Maßstab des Problems bezeichnet. Wenn sich n ständig ändert, ändert sich auch die Zeitfrequenz T(n). Aber manchmal möchten wir wissen, welches Muster es zeigt, wenn es sich ändert. Zu diesem Zweck führen wir das Konzept der Zeitkomplexität ein.

Im Allgemeinen ist die Anzahl der wiederholten Ausführungen grundlegender Operationen in einem Algorithmus eine Funktion der Problemgröße n, dargestellt durch T(n), so dass, wenn n nähert sich Im Unendlichen der Grenzwert von T(n)/f(n) einer Konstante ungleich Null, dann soll f(n) eine Funktion in der gleichen Größenordnung wie T(n) sein. 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. 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 Größenordnung angeordnet, umfassen häufige Zeitkomplexitäten:
Konstante Ordnung O(1), logarithmische Ordnung O(log2n) (Logarithmus von n mit Basis 2, dasselbe 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), exponentielle Ordnung O (2^n). Mit zunehmender Problemgröße n nimmt die oben genannte Zeitkomplexität weiter zu und die Ausführungseffizienz des Algorithmus wird geringer.
Zeitleistungsanalyse des Algorithmus
(1) Zeitaufwand des Algorithmus und Häufigkeit der Anweisung

Zeitaufwand eines Algorithmus = Summe der Ausführungszeit jeder Anweisung im Algorithmus

Die Ausführungszeit jeder Anweisung = die Anzahl der Ausführungen der Anweisung (dh Häufigkeit (Frequency Count)) × die Zeit, die zum einmaligen Ausführen der Anweisung erforderlich ist

Nachdem der Algorithmus in ein Programm umgewandelt wurde, die Zeit Die zum Ausführen jeder Anweisung erforderliche Leistung hängt von Faktoren ab, die schwer zu bestimmen sind, wie z. B. der Befehlsleistung der Maschine, der Geschwindigkeit und der Qualität des durch Kompilierung generierten Codes.

Um den Zeitverbrauch eines Algorithmus unabhängig von den Software- und Hardwaresystemen der Maschine zu analysieren, gehen Sie davon aus, dass die Zeit, die zum einmaligen Ausführen jeder Anweisung erforderlich ist, eine Zeiteinheit ist und der Zeitverbrauch eines Algorithmus alle Anweisungen in der Algorithmus. Die Summe der Frequenzen.
Um das Produkt C=A×B zweier quadratischer Matrizen n-ter Ordnung zu finden, lautet der Algorithmus wie folgt:

　　# define n 100 // n 可根据需要定义,这里假定为100
　　void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n])
　　{ //右边列为各语句的频度
　　int i ,j ,k;
　　 for(i=0; i<n;j++) n+1
　　 for (j=0;j<n;j++) { n(n+1)
　　 C[i][j]=0; n
　　 for (k=0; k<n; k++) nn(n+1)
　　 C[i][j]=C[i][j]+A[i][k]*B[k][j];n
　　}
　　}

Die Summe der Häufigkeiten aller Aussagen im Algorithmus (d. h. die Zeit der Algorithmuskosten) ist:

T(n)=nn(n+1) (1.1)

Analyse:

Die Schleifenkontrollvariable i der Anweisung (1) auf n erhöht werden sollte, wird der Test erst beendet, wenn i=n festgelegt ist. Daher ist seine Frequenz n+1. Der Schleifenkörper kann jedoch nur n-mal ausgeführt werden. Anweisung (2) sollte als Anweisung im Schleifenkörper von Anweisung (1) n-mal ausgeführt werden, Anweisung (2) selbst muss jedoch n+1-mal ausgeführt werden, sodass die Häufigkeit von Anweisung (2) n( n+1). Ebenso sind die Häufigkeiten der Sätze (3), (4) und (5) n, nn(n+1) bzw. n.

Der Zeitverbrauch T(n) des Algorithmus MatrixMultiply ist eine Funktion der Matrixordnung n3.

(2) Problemskala und Zeitkomplexität des Algorithmus
Die Eingabemenge des Algorithmus zur Lösung des Problems wird als Größe des Problems (Size) bezeichnet und im Allgemeinen durch eine ganze Zahl dargestellt.

Der Maßstab des Matrixproduktproblems ist die Ordnung der Matrix.

Die Größe eines graphentheoretischen Problems ist die Anzahl der Eckpunkte oder Kanten im Graphen.

Die Zeitkomplexität (Zeitkomplexität, auch Zeitkomplexität genannt) T(n) eines Algorithmus ist der Zeitverbrauch des Algorithmus und eine Funktion der Größe n des vom Algorithmus gelösten Problems. Wenn sich die Größe des Problems n der Unendlichkeit nähert, wird die Größenordnung (Ordnung) der Zeitkomplexität T(n) als asymptotische Zeitkomplexität des Algorithmus bezeichnet.

Die Zeitkomplexität T(n) des Algorithmus MatrixMultidy ist in Gleichung (1.1) dargestellt. Wenn n gegen Unendlich geht, gibt es offensichtlich T(n)~O(n3);

Dies zeigt, dass das Verhältnis von T(n) und n3 eine Konstante ungleich Null ist, wenn n groß genug ist. Das heißt, T(n) und n3 liegen in der gleichen Größenordnung oder T(n) und n3 liegen in der gleichen Größenordnung. Bezeichnet als T(n)=O(n3) ist es die asymptotische Zeitkomplexität des Algorithmus MatrixMultiply.

(3) Die asymptotische Zeitkomplexität bewertet die Zeitleistung eines Algorithmus.

Verwendet zur Bewertung hauptsächlich die Größenordnung der Zeitkomplexität des Algorithmus (dh die asymptotische Zeitkomplexität des Algorithmus). die Zeitleistung eines Algorithmus.
Die zeitliche Komplexität des Algorithmus MatrixMultiply beträgt im Allgemeinen T(n)=O(n3) und f(n)=n3 ist die Häufigkeit der Aussage (5) im Algorithmus. Als nächstes geben wir ein Beispiel, um zu veranschaulichen, wie man die zeitliche Komplexität des Algorithmus ermittelt.

Tauschen Sie den Inhalt von i und j aus.

Temp=i;
i=j;
j=temp;

　　以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。　　
注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
变量计数之一：

　　 x=0;y=0;
　　 for(k-1;k<=n;k++)
　　 x++;
　　 for(i=1;i<=n;i++)
　　 for(j=1;j<=n;j++)
　　 y++;

一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n2，所以该程序段的时间复杂度为T(n)=O(n2)。

当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

变量计数之二：

x=1;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;

该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：

则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)。

（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。

在数值A[0..n-1]中查找给定值K的算法大致如下：

i=n-1;
while(i>=0&&(A[i]!=k))
 i--;
return i;

此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:

①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；

②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。

Das obige ist der detaillierte Inhalt vonWie misst man die Ausführungszeiteffizienz eines Algorithmus?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!