big-o - コードフラグメントの漸近解析

Question

次のフラグメントのビッグ O 実行時間を見つける必要があります。

sum =0; 
for (int i=1; i<n; i++) {
  for (int j=1; j< n/i; j++) {
    sum = sum +j;
  }
}

外側のループが O(n) であることはわかっていますが、内側のループの分析に問題があります。O(log n)だと思います。

Answer 1

これをこの擬似数学スタイルで書きましょう。

sum i <- [1..n] (sum j <- [1..n/i] 1)

内側のループ (合計) が必要

n / i

繰り返し、それは項全体を作ります

sum i <- [1..n] (n/i)

分配法則に従って和を簡約する：

n * (sum i <- [1..n] (1/i))

1/x内和は、対数である上の積分にほぼ似ています。

そうO(n log n)です。

Answer 2

これに対する最善のアプローチは、アルゴリズムが実行するステップ数を検討することです。

n 個の要素がある場合、外側のループが少なくとも n 回実行されることがわかります。したがって、少なくとも O(n) である必要があります。

各 i に対して内側のループを何回実行する必要がありますか? i が増加するにつれて、それは増加しますか、同じままですか、それとも減少しますか?

i が増加すると内側のループのステップ数が減少することは明らかであり、さらに重要なことに、それは非線形的に減少します。つまり、O(n^2) ほど悪くないことがわかります。

したがって、それは O(n) と O(n^2) の間のどこかにあります.... 内側のループでステップがどのように減少するかについてもう少し分析すると、そこにたどり着くはずです。編集：...人々はすでにそれを配ったように見えますが:)

Answer 3

デイブが言ったように、内側のループは O(log n) であるため、O(n log n) です。