algorithm - 与大O有关的困惑

Question

我在研究时空复杂度时遇到了这个问题

O(n + (n/2 + n/4 .... n/n)) = O(n + log(n))。

我不明白这是怎么回事？谁能提供一些见解？

Answer 1

我认为这取决于您的分母。总结

n + n / 2 + n / 4 + n / 8 + ... + n / n

总和为 O(n)，因为它等于

n (1 + 1/2 + 1/4 + 1/8 + ...)

≤ 2n

因此，从技术上讲它是 O(n + log n) 是正确的，因为 O(n + log n) = O(n)，但这是一种非常奇怪的写法。 O(n) 是一种更好的写法。

总结

n + n/2 + n/4 + n/6 + n/8 + ... + n / n

锻炼到

n (1 + 1/2 + 1/4 + 1/6 + 1/8 + ... + 1/n)

= n (1 + (1/2) * (1 + 1/2 + 1/4 + 1/6 + ... + 1/(n/2)))

= n (1 + (1/2)H_{(n/2)})

= Θ(n log n)

这是有效的，因为 nth harmonic number是 Θ(log n)。这可能更接近预期，但将 + 替换为 ×。

希望这对您有所帮助!