Wie findet man diese Funktionskomplexität?

Question

Ich habe log n aber es ist nicht log n es ist log (log n)
aber warum?

int function(int n){ 
    return aux(n , 2) 
} 

int aux(int n, int x){ 
    while (n<x) { 
    x *= x; 
    } 
    return x; 
} 

, was die Komplexität der Funktion?

Answer 1

Ziemlich sicher, dass die Schleife Bedingung n > x sein soll, so werde ich es in dieser Antwort annehmen.

Zuerst beachten Sie die Werte von x:

x1 = x0 * x0 
    = 2 * 2 
    = 2^2 
x2 = x1 * x1 
    = x0 * x0 * x0 * x0 
    = 2 * 2 * 2 * 2 
    = 2^4 
x3 = x2 * x2 
    = x1 * x1 * x1 * x1 
    = x0 * x0 * x0 * x0 * x0 * x0 * x0 * x0 
    = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 
    = 2^8 

Wir sehen, dass der Exponent wächst als 2^t wo t die Anzahl der Iterationen in der Schleife ist, so dass wir die geschlossene Form Gleichung für x erhalten:

x = 2^(2^t) 

Dann können wir für die Anzahl der Iterationen lösen t:

n > x 
=> n > 2^(2^t) 
=> log(n) > 2^t 
=> log(log(n)) > t 

wie erforderlich.