我在研究空间和时间复杂性，遇到了这个问题。
O（N+（N/2+N/4….）n/n））=o（n+log（n））。
我不明白这是怎么回事有人能提供一些见解吗？
最佳答案
我想这取决于你的分母。总和
N+N/2+N/4+N/8+…+不适用
求和为O（n），因为它等于
N（1+1/2+1/4+1/8+…）
不大于2n
因此，从技术上讲，它是o（n+logn）是正确的，因为o（n+logn）=o（n），但这是一种非常奇怪的编写方法。O（n）是一个更好的方式来写出来。
总和
N+N/2+N/4+N/6+N/8+…+不适用
努力
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（1+（1/2）小时{（n/2）}）
=_（n对数n）
这是因为nth harmonic number是（log n）这可能更接近预期，但用+替换为×。
希望这有帮助！
关于algorithm - 与大O相关的困惑，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26498716/