與大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）的。這可能與預期的更接近，但用+ ×代替。

希望這會有所幫助！