どのようにこの関数の複雑さを見つけるのですか？

Question

ログnを取得しましたが、ログnではありません。ログ（ログn）
ですが、なぜですか？

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

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

機能の複雑さは何ですか？

Answer 1

ループの状態がn > xであることを確かめておいてください。私はこの答えで推測しています。

まず、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 

私たちは、指数は、我々はxのための閉じた形の方程式を得ることができるようにtは、ループ内の繰り返しの数である2^tとして成長していることを参照してください。

01：

x = 2^(2^t) 

その後、我々は、反復tの数について解くことができます

必要に応じて