与大O混乱

Question

我工作的空间和时间复杂度和过这个

Ó来了（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 + 2 + 1/4 + 1/6 + ... + 1 /（n/2）））

= N（1 +（1/2）H _ {（N/2）}）

= Θ（N log n）的

此工作，因为nth harmonic number Θ是（log n）的。这可能与预期的更接近，但用+ ×代替。

希望这会有所帮助！