Laufzeit von Programm finden - C ++, Leistung, Algorithmus

Ich bin neu in Algorithmen und DS. Ich beziehe mich auf ein Buch und es gibt einige Fragen, die mir schwer verständlich sind.

Ich muss die Laufzeit der folgenden Programme ermitteln: (die Kommentare stammen nur aus dem Buch)

function(int n) {
for(int i=1;i<=n/3;i++) { // will execute n/3 time
for(int j=1;j<=n;j+=4) { // will execute n/4 times
printf("*");
}
}
}

Antwort: O (n ^ 2)

Wie ist es n ^ 2? Die erste Schleife wird für n / 3 und die zweite für n / 4 ausgeführt. n / 3 * n / 4 = n ^ 2/12. Wie ist es n ^ 2? Bitte hilf mir zu verstehen.

Frage 2

function(int n) {
for(int i=0;i<n;i++) { // will execute n times
for(int j=i;j<i*i;j+=4) { // will execute n*n times ?????? (How?)
if(j%i==0) {
for(int k=0;k<j;k++) { // will execute j times
printf("*");
}
}
}
}
}

Antwort: O (n ^ 5)

Die erste Schleife wird n-mal ausgeführt. Fein.

Wie läuft die zweite Schleife n * n mal ab? Hier wird der Wert von j auf i initialisiert, also sollte es nicht (n * n) -i mal sein? Wenn j auf 0 initialisiert wurde, wäre es n * n mal gewesen, oder?

Die dritte Schleife führt j mal aus, da k

Bitte helfen Sie mir zu verstehen, warum die 2. Schleife (j) n * n-mal ausgeführt wird. Vielen Dank.

Antworten:

0 für die Antwort № 1

Das Buch handelt von Big-Oh. Eine vollständige Einführung in Big-Oh wäre zu lang, aber in Big-Oh-Land heißt es:

O(a*f(n)) = O(f(n))

mit a eine Konstante.

ein anderes ist das:

O(a_k * n^k+ a_(k-1) n^(k-1)+...+a_0) = O(n^k)

mit f(n) eine zufällige Funktion.

---

Über die zweite Frage: Die zweite Schleife läuft ab i zu i*i. Jetzt seit i wird erreichen n-1 es hat größe O(n)Die Schleife wird also im letzten Lauf ausgeführt (n-1)*(n-1) mal. Schon seit j wird irgendwann etwas von der Ordnung erreichen O(n^2) und die dritte Schleife läuft ab 0 zu j-1Die dritte (innerste) Schleife hat eine zeitliche Komplexität von O(n^2) auch. Dies bedeutet also, dass die Gesamtzeitkomplexität der Schleifen folgendermaßen ist:

O(n)*O(n^2)*O(n^2)=O(n^5)

---