与Big 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)

这是因为n次谐波数是Θ(log n).这可能更接近预期,但用+替换为×.

希望这可以帮助!