Beispiel-Tutorial zur Konzeptkompetenz der Darstellung von Python-Algorithmen

In diesem Artikel wird hauptsächlich das Python-Algorithmus-Repräsentationskonzept im Detail vorgestellt, das einen bestimmten Referenzwert hat.

In diesem Artikel wird das Python-Algorithmus-Repräsentationskonzept für alle erläutert. Der spezifische Inhalt lautet wie folgt:

Konstante Ordnung O(1)

Konstante wird auch als feste Zahl bezeichnet, die sich auf eine Konstante bezieht, deren numerischer Wert sich nicht ändert. Das Gegenteil ist Variable

Warum ist die Zeitkomplexität des folgenden Algorithmus nicht O(3), sondern O(1).

int sum = 0,n = 100; /*执行一次*/ 
sum = （1+n）*n/2; /*执行一次*/ 
printf（"%d", sum）; /*行次*/

Die Anzahl der Durchläufe dieses Algorithmus beträgt f(n)=3. Gemäß unserer Methode zur Ableitung der großen O-Ordnung besteht der erste Schritt darin, den konstanten Term 3 in 1 zu ändern. Bei der Beibehaltung des Termes höchster Ordnung haben wir festgestellt, dass dieser überhaupt keinen Term höchster Ordnung hat, sodass die zeitliche Komplexität dieses Algorithmus O(1) beträgt.

Stellen wir uns außerdem vor, dass, wenn es in diesem Algorithmus 10 Aussagen sum=(1+n)*n/2 gibt, das heißt:

int sum = 0, n = 100; /*执行1次*/ 
sum = （1+n）*n/2; /*执行第1次*/ 
sum = （1+n）*n/2; /*执行第2次*/ 
sum = （1+n）*n/2; /*执行第3次*/ 
sum = （1+n）*n/2; /*执行第4次*/ 
sum = （1+n）*n/2; /*执行第5次*/ 
sum = （1+n）*n/2; /*执行第6次*/ 
sum = （1+n）*n/2; /*执行第7次*/ 
sum = （1+n）*n/2; /*执行第8次*/ 
sum = （1+n）*n/2; /*执行第9次*/ 
sum = （1+n）*n/2; /*执行第10次*/ 
printf（"%d",sum）; /*执行1次*/

Tatsächlich, egal was passiert n ist, die beiden oben genannten Codeteile sind der Unterschied zwischen 3 und 12 Ausführungen. Dieser Algorithmus hat unabhängig von der Größe des Problems (der Größe von n) eine konstante Ausführungszeit und wird als Zeitkomplexität von O(1) und auch als konstante Ordnung bezeichnet.

Hinweis: Egal um welche Konstante es sich handelt, wir werden sie als O(1) aufzeichnen, nicht als irgendeine andere Zahl wie O(3), O(12) usw. Dies ist ein Fehler, den oft gemacht wird Anfänger.

Ableitung der Big O-Methode

1 Ersetzen Sie alle additiven Konstanten in der Laufzeit durch die Konstante 1

2 . In der modifizierten Anzahl der Läufe wird nur der Term höchster Ordnung

3 beibehalten. Wenn der Term höchster Ordnung vorhanden ist und nicht 1 ist, entfernen Sie die Konstante

wird mit diesem Term multipliziert. Logarithmische Ordnung O(log2n)　

Logarithmus

Wenn a hoch x gleich ist zu N (a>0 und a ist nicht gleich 1), dann wird die Zahl x als Logarithmus von N mit a als Basis (Logarithmus) bezeichnet, aufgezeichnet als x=logaN, . Unter diesen wird a als Basis des Logarithmus und N als reelle Zahl bezeichnet.
5^2 = 25, aufgezeichnet als 2= log5 25
Logarithmus ist eine Operation und Exponential ist eine reziproke Operation. Zum Beispiel

① 3^2=9 <==> 2=log<3>9; 3 /2=log<4>8;

③ 10^n=35 <==> Zur Vereinfachung der Verwendung werden die häufig verwendeten Logarithmen mit der Basis 10 nach und nach als lgN aufgezeichnet. Nach der Multiplikation der Zählzeiten mit 2 liegt es einen Punkt näher an n.

Mit anderen Worten, wie viele Zweien multipliziert größer als n sind, dann wird die Schleife beendet.

Aus 2^x=n erhalten wir x=log2n. Die zeitliche Komplexität dieser Schleife beträgt also O(logn). Lineare Ordnung O(n)　

int count = 1; 
while (count < n) 
{  
count = count * 2; /* 时间复杂度为O(1)的程序步骤序列 */ 
}

Die Ausführungszeit steigt proportional mit der Problemgröße

Lineare logarithmische Ordnung O ( nlog2n)

quadratische Ordnung O(n^2)

data = [ 8,3,67,77,78,22,6,3,88,21,2]
find_num = 22
for i in data:
  if i == 22:
    print("find",find_num,i )

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. ​

Das obige ist der detaillierte Inhalt vonBeispiel-Tutorial zur Konzeptkompetenz der Darstellung von Python-Algorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!