Identifizieren Anzahl der Iterationen der while-Schleife

Question

ich diesen Code von meinem Computer Science-Klasse haben:

int input=15; 
while (input < n) { input = input *3;} 

Dieser Code die Obergrenze von log 3 hat (n/15) Schleifen. Wie können wir dieses Ergebnis erzielen?

Answer 1

Ich denke, er spricht über die analytische Lösung der Komplexität. Ich denke, es ist so etwas wie diese (schon vor langer Zeit ich habe logaritms):

15 * 3^x = n // x would be the number of iterations until value reaches n 

ln(15*(3^x)) = ln(n) 
ln(15) + ln(3^x) = ln(n) 
ln(15) + x*ln(3) = ln(n) 
x = (ln(n) - ln(15))/ln(3) 
x = ln(n/15)/ln(3) 
x = log3(n/15)/log3(3) 
x = log3(n/15) 

Answer 2

Für welche Werte von n wird der Code Schleife k mal?

Es muss, dass 15 < n, und 15 * 3 < n und 15 * 3 * 3 < n und .... und 15 * 3^(k-1) n <. Es muss auch sein, dass 15 * 3^k> = n (sonst würde der Code mindestens eine weitere Schleife tun).

Das heißt, 3^k> = n/15> 3^(k-1), und Logs (Basis 3), k> = log3 (n/15)> k-1.

Somit ist k die kleinste ganze Zahl größer oder gleich log3 (n/15), oder äquivalent: k = ceil (log3 (n/15)) wie erforderlich.