algorithm - 複雑さ アルゴリズム 再帰関係

Question

int function(int n){
if (n<=1)
 return 1;
else 
 return (2*function(n/2));
}

実行時間 の再帰関係 T(n) とは何ですか? またその理由は?

Answer 1

直接計算できます。これは、最も近い 2^n、最大または等しいです。

L=log2(n) を計算すると、2^L または 2^(L+1) が得られます。

複雑さは O(log2 N) : log2 N 操作です。

Answer 2

このアルゴリズムの複雑度関数は次のようになります。

T(n) = T(n / 2) + 1
T(1) = 1

マスター定理を適用すると、次のようになります。

a = 1
b = 2
c = 0 (1 = n^0)

log b(A) = log2(1) = 0 = 0 c, thus case 2
apply values and the result is O(log n).

@guillaumeがすでに正しく述べているように、これは線形関数を使用することではるかに簡単に解決できます。