12 
int foo(int n) 
{
    int x=2;
    while (x<n)
    {
        x = x*x*x;
    }

    return x;
}

その時間の複雑さを分析する必要があります。nよりもはるかに速く到達することに気付きましたlog(n)。つまり、実行するよりも少ないステップを実行O(log(n))します。私は答えを読みましたが、彼らがどのようにしてそれにたどり着いたのかわかりません:それはO(log(log(n)). さて、あなたはそのような質問にどのようにアプローチしますか?

4

7 に答える 7

9

それを再帰関数と考えてください:

f(i) = f(i-1)^3

展開した場合：

f(i) = ((f(i-k)^3)^3)[...k times] = f(i-k)^(3^k) = f(0)^(3^i)

関数は累乗の累乗として成長します...したがって、特定の数に達するまでの時間（反復）（つまり、関数の逆数を計算する）は、対数の対数です。

あなたの例のように、いつ入力パラメーター（および反復回数）f(0) = 2になるかを知りたいです。f(i) >= nni

f(i) = 2^(3^i) >= n
           3^i >= log_2(n)
             i >= log_3(log_2(n))

したがって、 の値に到達するにはn、takes log_3(log_2(n))反復します (整数を処理しながら切り上げてそれを超えます)。

関数が次の場合：

f(i) = 2*f(i-1) //e.g. x=2*x

その場合、パターンは次のようになります。

f(i) = 2*2*[...k times]*f(i-k) = f(i-k)*(2^k) = f(0)*(2^i)

この場合、関数の逆数は底 2 の単対数になります。

私の計算はあまり厳密ではありませんが、理解していただければ幸いです。

于 2009-09-16T15:12:44.333 に答える
2

させて

L3 = 基数 3 への ログL2 = 基数 2 へのログ

その場合、正解はO(L3(L2(n))であり、O(L2(L2(n))) ではありません。

x = x * 2から始めます。x は n に達するまで指数関数的に増加するため、時間計算量は O(L2(n)) になります。

x = x * xを考えてみましょう。x は上記よりも速く増加します。すべての反復で、x の値は前の値の 2 乗にジャンプします。簡単な計算をすると、次のようになります。

x = 2 n = 4 の場合、反復回数 = 1 n = 16、反復回数 = 2 n = 256、反復回数 = 3 n = 65536、反復回数 = 4

したがって、時間計算量はO(L2(L2(n))です。これは、n の値の上に値を入れることで確認できます。

今あなたの問題に来て、x = x * x * x。これは、x = x * x よりもさらに速く増加します。ここに表があります：

x = 2 n = 8 の場合、反復回数 = 1 n = 512、反復回数 = 2 n = (512*512*512)、反復回数 = 3 など

これを注意深く見ると、これはO(L3(L2(n))であることがわかります。 L2(n) は 2 のべき乗を取得しますが、すべての反復で x の立方体を取得しているため、次のようにする必要があります。実行された正しい反復回数を調べるために、ログを底 3 にします。

したがって、正解はO(log-to-base-3(log-to-base-2(n))だと思います

これを一般化すると、x = x * x * x * x * .. (k times)の場合、時間の計算量はO(log-to-base-k(log-to-base-2(n)

于 2009-09-17T02:05:19.633 に答える
1

反復iステップの数と後のステップx(i)の値とします。我々は持っていますxi

x(0) = 2
x(i) = x(i-1)³

総ステップ数が最大iなので、x(i) < n。

我々は持っています

log x(i) = log x(i-1)³
         = 3·log x(i-1)
         = 3·log x(i-2)³
         = 3²·log x(i-2)
         = 3^i·log x(0)
         = 3^i·log 2

⇒  log log x(i) = log (3^i·log 2)
                 = log 3^i + log log 2
                 = i·log 3 + log log 2

対数は厳密に増加しているので、

x(i) < n ⇔        log log x(i) < log log n
         ⇔ i·log 3 + log log 2 < log log n
         ⇔                   i < (log log n - log log 2) / log 3 ∈ O(log log n)
于 2009-09-17T16:19:58.097 に答える