0

次の質問に問題がありました

次のネストされたループ構造を考えてみましょう。「big-o」表記を使用して、変数 n に関してその効率を分類します。省略記号 (...) で表されるステートメントが、4 つのメイン メモリ アクセス (それぞれに 1 マイクロ秒を必要とする) と 2 つのディスク ファイル アクセス (それぞれに 1 ミリ秒を必要とする) を必要とするとします。n が 1000 の場合に、この構文の実行に必要な時間をミリ秒で表します。

x = 1;
do
{
    y = n;
    while (y > 0)
    {
    ...
        y--;
    }
    x *= 2;
} while (x < n*n);
4

2 に答える 2

1

y の内側のループは O(n) です。

外側のループは、x = 1、2、2^2、2^3、... 2^k < n * n で実行されます。したがって、O(2 * log(n)) である O(log(n*n)) で実行されます

したがって、複雑さは O(n * log(n)) です

于 2013-09-25T18:29:07.780 に答える
0

他の答えにもう少し説明を加えるために、コードの注目すべき部分は x *= 2; です。つまり倍増。したがって、この部分は線形ではありません。したがって、log2 を考える必要があります。

したがって、x は log2(n*n) で n*n に達します。= log2(n^2) = 2 x log2(n)。

y カウントダウンは線形です。つまり、O(n) です。

ループ内にループがあるため、次のように両方の操作を乗算します。

n * 2 x log2(n) = O(n * 2 * log2(n))。次に、取得する定数係数を取り出します: O(n * log2(n))

于 2013-09-25T18:40:17.073 に答える