コードの時間複雑性分析

StackOverflow https://stackoverflow.com/questions/1433530

  •  07-07-2019
  •  | 
  •  

質問 

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))です。さて、そのような質問にどのようにアプローチしますか？

役に立ちましたか？

解決

しましょう

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回）の場合、時間の複雑さは O（log-to-base-k（log -to-base-2（n）

他のヒント

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

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) >= nがn入力パラメーター（およびi反復数）である場合を知りたい：

f(i) = 2^(3^i) >= n
           3^i >= log_2(n)
             i >= log_3(log_2(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の単一の対数になります。

私の数学はそれほど厳密ではありませんが、アイデアが得られることを願っています。

ループの反復回数でxがどのように変化するかを考えてください。毎回、キューブします。したがって、i回の反復後、値は2キューブになり、再びキューブになります...など、i回です。この式を示すためにx（i）を使用しましょう。 x（0）= 2、x（1）= 2 3などとしましょう（a bを使用して、bのべき乗を意味します）。

x（i）<！> gt; = nの場合は完了です。それはどのくらいかかりますか？ iで解決しましょう。

First, we take a log on both sides: ln(x(i))>=ln(n)

ln(x(i)) = ln(x(i-1))*3 = ln(x(i-2))*(3**2) = ... = ln(x(0))*(3**i)

(the above uses [this property][1]: ln(x**b)==ln(x)*b)

so, 3**i * 2 >=ln(n). Let's take another logarithm:

ln(3**i * 2) = ln(2) + ln(3)*i 

so ln(2) + ln(3)* i >= ln(ln(n))

Now we can solve for i: i >= ( ln(ln(n))-ln(2) ) / ln(3)

定数の要因は無視できますが、log（log（n））ステップを実行するという結論が残っています。それがアルゴリズムの複雑さです。

うまくいけば、そのようなすべてのステップを分解するのに役立ちます。

whileループ内のコードがあった場合

x = 2*x;

xは、O（log（n））反復でnに達します。 xを定数で乗算するのではなく、立方体にしているので、nに速く到達します。

指定

log ( A * x )     == log ( A ) + log ( x )
log ( x * x * x ) == 3 * log ( x )

そう

log ( log ( x * x * x ) ) == log ( 3 * log ( x ) )
                          == log ( 3 ) + log ( log ( x ) )

この関数は、あなたの関数よりもどれくらい速くまたは遅くなりますか（ループの反復回数で測定）？

int log_foo ( int n ) 
{
    double          log_x = log ( 2 );
    const double    log_n = log ( n );

    while ( log_x < log_n )
    {
        log_x = 3 * log_x;
    }

    return exp ( log_x );
}

そして、この関数はあなたの関数よりどれくらい速く、または遅くなりますか？

int log_log_foo ( int n ) 
{
    double          log_log_x = log ( log ( 2 ) );
    const double    log_log_n = log ( log ( n ) );
    const double    log_3     = log ( 3 );

    while ( log_log_x < log_log_n )
    {
        log_log_x += log_3;
    }

    return exp ( exp ( log_log_x ) );
}

ただし、この関数は定数でlog_log_xをインクリメントするだけなので、反復回数を簡単に計算できます。

Let iを反復ステップの数とし、x(i)の値をxステップの後のx(i) < nにします。 

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

ステップの総数は最大の<=>なので、<=>になります。

持っています

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)

ループの反復回数をカウントするカウンター変数を追加しない理由。関数が戻る直前に出力します。

次に、値の範囲に対して関数を呼び出します。最初は3〜1,000,000。次に、 GNUPlot のようなものを使用して結果をプロットします。

次に、グラフが既知の曲線と一致するかどうかを確認します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top