我需要找到以下片段的大 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)。
让我们用这种伪数学风格来写这个。
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)
是对的。
最好的方法是考虑算法将采取多少步。
如果你有 n 个元素,你就知道外循环将至少运行 n 次。所以它必须至少为 O(n)。
对于每个 i,内部循环必须运行多少次?它会随着 i 的增加而增加、保持不变还是减少?
很明显,内循环的步数会随着 i 的增加而减少,更重要的是,它会非线性地减少。所以你知道它没有O(n ^ 2)那么糟糕。
所以它介于 O(n) 和 O(n^2) 之间......关于内部循环中的步骤如何减少应该让你到达那里的更多分析。编辑:......虽然看起来人们已经放弃了它:)
正如戴夫所说,它是 O(n log n),因为内部循环是 O(log n)。