Zeit Komplexität der Programme

Question

Ich lerne gerade über die Zeit Komplexität, hier ist Teil des Codes I

for (int i = 1; i <= N; i++) 
    for (int j = 1; j <= N; j++) 
    { 
    // Spread Peace 
    } 

klar, dass die oben ein geschrieben habe, ist von O (N^2) Komplexität und sein scheint (für N == 1e6) für immer laufen. Hier

Sekunden ist Stück Code

for (int i = 1; i <= N; i++) 
    for (int j = i; j <= N; j++) 
    { 
    // Money is Everything 
    } 

die obige ist auch O (N^2) - N * (N + 1)/2 Komplexität auch immer ausgeführt wird, aber dieser Code:

for (int i = 1; i <= N; i++) 
    for (int j = i; j <= N; j += i) 
    { 
    // Be my GirlFriend 
    } 

führt nur innerhalb einer Sekunde. ich bin nicht in der Lage seine Zeitkomplexität abzuleiten, warum dies so schnell? Was ist die Schätzung für N == 1e6?

Answer 1

das Lassen Sie sich ein Experiment zuerst durchführen, lassen die Schleife (C# -Implementierung) Abrollen versuchen und schauen, was los ist:

private static IEnumerable<String> Unroll(int N) { 
    for (int i = 1; i <= N; i++) { 
    StringBuilder sb = new StringBuilder(); 

    for (int j = i; j <= N; j += i) { 
     if (sb.Length > 0) 
     sb.Append(", "); 

     sb.Append(j); 
    } 

    yield return sb.ToString(); 
    } 

Ein Testlauf mit einer geringen Anzahl (zB 16) zeigt das Bild

Console.Write(string.Join(Environment.NewLine, Unroll(16))); 

können Sie das Muster zu sehen, ein Exponent ial fallen lassen? Es sieht aus wie N * log(N), richtig?

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 
2, 4, 6, 8, 10, 12, 14, 16 
3, 6, 9, 12, 15 
4, 8, 12, 16 
5, 10, 15 
6, 12 
7, 14 
8, 16 
9 
10 
11 
12 
13 
14 
15 
16 

Jetzt ist es Zeit für das Papier und Bleistift: wir haben (für große N)

N/1 items (step == 1) + 
    N/2 items (step == 2) + 
    N/3 items (step == 3) + 
    ... 
    N/N items (step == N) 
------------------------------ 
    N * (1 + 1/2 + ... + 1/N) = 
    N * H(N) = 
    O(N * log(N)) // Harmonic sum H(N) gives log(N) 

genauere Schätzung

H(N) = ln(N) + gamma + 1/(2*N) + ... 

wo

ln() - natural logarithm 
    gamma - Euler–Mascheroni constant (0.5772156649...) 

Sie gibt für N == 1e6 über 14.4e6 Schleifen, die in der Tat ist ein bisschen überschätzt; der tatsächliche Zählwert 13970034 (14.0e6), da, wenn sie mit Naturtonreihe aproximating wir ganzzahlige Division nehmen did't berücksichtigt (jeweils k/N sollte integer, das heißt nicht k/N, aber floor(k/N) sein).

Answer 2

Sie gehen kann Sigma-Notation:

Mehr auf Harmonic Funktionen hier: Asymptotic analysis