Wie finden Sie die Laufzeit von Schleifen, die sich gegenseitig beeinflussen?

Question

Ich bin der Fachbegriff für diese Art von Schleifen nicht sicher (falls vorhanden auch), so dass ich ein Beispiel nennen:

x=0 
i = 1 
while(i<n) 
    for(j=1 to n/i) 
     x = x + (i-j) 
    i*=2 
return(x) 

In diesem Beispiel wird die while-Schleife ändert direkt die Anzahl der Male des For Schleife läuft, die mich aus irgendeinem Grund wirft

Normalerweise würde ich Zeile für Zeile gehen und sehen, wie oft jede Zeile ausgeführt würde, aber weil die Anzahl der Male ändert, habe ich versucht, eine Summierung, aber bekam eine wenig verloren ... Was wäre ein Schritt für Schritt Weg, um diese Art von Problem zu lösen?

Die Antwort im Anhang ist O (n), aber wenn ich das tat ich bekam nlog (n)

Jede Hilfe sehr geschätzt wird, ist diese Bewertung für meinen letzten

Auch, wenn Sie wissen, von irgendwelchen guten Orten, um Übungsaufgaben dieser Art zu finden, würde ich es schätzen!

Danke

Answer 1

ich die Analyse an diesem Code denken in diesem lecture auf die sehr ähnlich ist, die Laufzeit des Verfahrens des Aufbaus einer max Haufen zu finden. Die einfache Analyse ergab keine Komplexität, aber wenn man sie mit Summierungen analysierte, stellte sich heraus, dass es genau wie dein Problem war.

Also zurück zu Ihrer Frage, die äußere Schleife läuft mal und der innere läuft n/i. Aber da ich exponentiell wächst, können wir eine andere Variable j verwenden, die einmal bei einer Schleifeniteration erhöht wird, so dass sie bei der Summierung verwendet werden kann und die Grenzen entsprechend der Relation ändern kann.

Die Summation ist Die Summe eine geometrische Sequenz Ergebnis dessen ist so dass, wenn n gegen unendlich geht, konvergiert auf einen konstanten (2). Daher wird die Summierung als konstanter Faktor betrachtet und beeinflusst nicht die asymptotische Komplexität des Codes, der nur O (n) ist.