Big O Notation HFG - Codefragment Algorithmus Analyse? [geschlossen]

Question

Für Hausaufgaben, wurde ich die folgenden 8-Codefragmente gegeben zu analysieren und eine Big-Oh-Notation für die Laufzeit zu geben. Kann jemand mir bitte sagen, ob ich auf dem richtigen Weg bin?

//Fragment 1
for(int i = 0; i < n; i++)
    sum++;

Ich denke O (N) für Fragment 1

//Fragment 2
for(int i = 0; i < n; i+=2)
    sum++;

O (N) für Fragment 2 und

//Fragment 3
for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

O (N ^ 2) für Fragment 3

//Fragment 4
for(int i = 0; i < n; i+=2)
    sum++;
for(int j = 0; j < n; j++)
    sum++;

O (N) für Fragment 4

//Fragment 5
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

O (N ^ 2) für Fragment 5, aber die n * n mich weg wirft ein bisschen so bin ich nicht ganz sicher,

//Fragment 6
for(int i = 0; i < n; i++)
    for( int j = 0; j < i; j++)
        sum++;

O (N ^ 2) für Fragment 6 als auch

//Fragment 7
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        for(int k = 0; k < j; k++)
            sum++;

O (N ^ 3) für Fragment 7, jedoch wiederum die n * n wirft me off

//Fragment 8
for(int i = 1; i < n; i = i * 2)
    sum++;

O (N) für Fragment 8

Answer 1

Ich glaube, Fragment 5 ist O (n ^ 3), und in ähnlicher Weise fragmentieren 7 O (n ^ 5) * ist. Es sieht auch wie O (log (n)) für Fragment 8.

Für die n * n Probleme, haben Sie den Körper der Schleife n * n-mal ausgeführt werden, so dass es sein würde, O (n ^ 2), man dann Verbindung, die mit der Ordnung des anderen Codes. Fragment 8 verdoppelt tatsächlich die Zähler statt Inkrementieren es, so je größer das Problem, desto weniger zusätzliche Arbeit, die Sie zu tun haben, so ist es O (log (n))

* edit: Fragment 7 ist O (n ^ 5), nicht O (n ^ 4) als I bisher angenommen. Dies liegt daran, sowohl j und k von 1 bis n * n gehen. Leider habe ich diese früher nicht fangen.

Answer 2

Fragment 7 ist O (n ^ 5), nicht O (n ^ 4) als die derzeit anerkannten Kommentar Ansprüche. Ansonsten ist es richtig.

Answer 3

Für Fall 8 versuchen, die Anzahl der Iterationen für einige Werte von N Schreiben und sehen, was das Muster wie ... sieht es nicht O (N)

Answer 4

Sie erscheinen auf dem richtigen Weg zu sein. In Bezug auf die N * N welche Auswirkungen denken Sie, hätte er? Es ist ein weiterer Faktor von N so würde es wahrscheinlich eine höhere Ordnung sein.

Nur eine Warnung, sah ich einen anderen Posten wie folgt und es war extrem nach unten gestimmt. Achtung. Hier ist die Post.

Answer 5

Sie sind auf dem richtigen Weg, aber hier ist ein Tipp, wie die Dinge könnten auf dem Weg klarer zu bekommen. Angenommen, Sie haben einen Code:

for(i = 0; i < n; i++) {
   for(j = 0; j < 100; j++){....}
}

Richtig, die Tatsache berücksichtigen, dass Sie Code auf verschiedenen Ebenen haben. In diesem Beispiel können Sie 3 Ebenen sehen nur so weit:

1. Die äußere for-Schleife, die von 0-n
geht
2. Ein weiterer for-Schleife, die von 0-100
geht
3. Einige Code innerhalb, dass als ... markiert

Zu keinem Zeitpunkt sollten Sie versuchen, sie alle in 1 gehen zu berechnen. Dies ist, wo die meisten Anfänger eine Art von arithmetischen Fehlern machen. Berechnen sie individuell für jede Ebene und dann multiplizieren sie alle zusammen.

Viel Glück!