代码片段的渐近分析

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)是对的.