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(n log n)，因为内部循环是 O(log n)。