Gibt es einen allgemeinen Weg, um die asymptotische Zeitkomplexität von for-Schleifen mit Schritt zu berechnen?

Question

Gibt es einen allgemeinen Weg/Ansatz/Methodik zur Berechnung der asymptotischen Zeitkomplexität solcher Schleifen?

j=a 
while j<n do 
    j=f(j) 

wo f(j) könnte j+1 sein, 2*j, j*j etc ..

Beachten Sie, dass der obige Code in die C-Schleife

for (j=a; j<n; j=f(j)); 

Answer 1

Der Ansatz der Wiederholung der Lösung ist

F(j+1) = f(F(j)), F(0) = a. 

dann die Lösung des inequation

F(k(n)) < n <= F(k(n)+1), 

für k(n) und die Komplexität ist O(k(n)).

Zum Beispiel ergibt f(j):= j²

F(j+1) = F²(j), F(0)= a 

, die die Lösung

F(j) = a^(2^j). 

Dann

durch Inversion hat

k(n) ~ log(log(n)/log(a))/log(2) = O(log(log(n))). 

Answer 2

Zuerst werden die Antworten entspricht, dann ist die allgemeine Ansatz:

1) Wenn f (j) = j + 1, dann haben Sie ungefähr n Schritte, um n zu erreichen.

2) Wenn es 2 * j ist. Jedes Mal, wenn Sie es in ungefähr log n Schritten verdoppeln, werden Sie n erreichen.

3) Wenn j * j, wird es a, a^2, a^4, a^8; Daher werden Sie in ungefähr loglog n Schritten zu n kommen.

Nun, was ist der allgemeine Weg? Sie finden das Muster und gleichen es zu n und dann lösen Sie die Gleichung:

1) Anwenden von f x mal erhalten Sie ein + x, also a + x = n so x = n - a = O (n).

2) Wenn Sie f x mal anwenden, erhalten Sie ein * (2^x), also a * (2^x) = n, also x = log n/a = O (log n).

3) Die Anwendung von fx-Zeiten gibt Ihnen ein^(2^x), also a^(2^x) = n also 2^x = log_a n, also x = log log_a n = O (log log n). (Log_a n log n mit einer Base)

Ich hoffe, es hilft