algorithm - 双 for 循环的最坏情况运行时间

Question

谁能解释一下在下面的练习中最坏情况下的运行时间是 O(N) 而不是 O(N^2)。有两个 for 循环，其中对于每个 i 我们需要将 j 与 i 进行比较，sum++ 然后递增并再次重复该操作直到达到 N。

以下代码片段最坏情况运行时间的增长顺序是什么作为 N 的函数？

int sum = 0;
for (int i = 1; i <= N; i = i*2)
    for (int j = 0; j < i; j++)
        sum++;

问题解释

答案是:N

内层循环体执行了 1 + 2 + 4 + 8 + ... + N ~ 2N 次。

Answer 1

我认为您已经在问题中给出了答案——内循环执行了 2N 次，即 O(N)。在渐近(或大 O)表示法中，任何倍数都被丢弃，因为对于非常非常大的值，2N 的图形看起来就像 N，因此它不被认为是重要的。在这种情况下，问题的复杂度等于调用“sum++”的次数，因为算法是如此简单。这有意义吗？