algorithm - 簡単な操作でアルゴリズム O(n^3 log n) を提供しますか?

Question

アルゴリズムの計算性能 O(n ³ log n) を提供します。アルゴリズムには、単純な操作のみを含める必要があります。

この問題にアプローチする方法について何か考えはありますか?...私はコンピュータ サイエンスの GRE のために勉強しています。ありがとう！

Answer 1

これを行う 1 つの方法は、O(n ³ ) 回実行する外側のループと、O(log n) 回実行する内側のループを作成することです。

for (int i = 0; i < n * n * n; i++) {
   for (int j = 1; j <= n; j *= 2) {
       // ... do nothing ... //
   }
}

^{ループを k 回繰り返した後の j の値は 2 k}であり、k ≥ lg n になるとすぐに j = 2 ^k ≥ nになるため、内側のループは log n 回実行されることに注意してください。

もう 1 つのオプションは、再帰関数を作成することです。その実行時間は、Master Theoremを介して O(n ³ log n) になります。これを行う 1 つの方法は、サイズ n / 2 の部分問題に対して 8 回の再帰呼び出しを行い、呼び出しごとに Θ(n ^{3 ) を実行する関数を用意することです。}

void silly(int n) {
    if (n > 0) {
        for (int i = 0; i < n * n * n; i++) {
            // ... waste time ... //
        }
        for (int i = 0; i < 8; i++) {
            silly(n / 2);
        }
    }
}

EDIT : @Nuclearman が指摘したように、クイックソートやヒープソートなどのアルゴリズムを使用してサイズ n ^{3の配列をソートすることにより、ランタイム O(n 3 log n) を取得することもできます。}より一般的には、ランタイムが O(n log n) であるアルゴリズムを、サイズが n ³の入力に対して実行すると、O(n ³ log n) のランタイムが生成されます。これは、log (n ³ ) = 3 log n = O(log n) という事実を利用しています。

お役に立てれば！