1

次のアルゴリズムの時間計算量を計算する方法。試してみましたが、再帰呼び出しのため混乱しています。 

power (real x, positive integer n)
//comment : This algorithm returns xn, taking x and n as input
{
    if n=1 then
    return x;
    y = power(x, |n/2|)
    if n id odd then
    return y*y*x //comment : returning the product of y2 and x
    else
    return y * y //comment : returning y2
}

誰かが簡単な手順で説明できますか。

4

2 に答える 2

1

再帰関数の時間計算量を把握するには、入力変数に関して行われる再帰呼び出しの数を計算する必要がありますN。

この場合、各呼び出しは最大 1 回の再帰呼び出しを行います。呼び出し回数は O(log 2 N) のオーダーです。これは、各呼び出しがN半分に減少するためです。

に依存しないため、再帰関数の本体の残りの部分は O(1)Nです。したがって、関数の時間の複雑さは O(log 2 N) です。

于 2013-09-06T17:18:29.443 に答える
0

各呼び出しは一定時間の操作と見なされ、再帰の回数は、n = 1 の前に n/2 を実行できる回数に等しく、最大で log 2 ( n) 回です。したがって、最悪の場合の実行時間は O(log 2n ) です。

于 2013-09-06T17:20:00.523 に答える