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

Question

谁能解释一下在下面的练习中，最坏情况运行的时间是 O(N) 而不是 O(N^2)。有两个 for 循环，其中对于每个 i 我们需要将 j 与 i 进行比较，求和 ++ 然后递增并再次重复该操作直到达到 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++"被调用的次数，因为算法是如此简单。这有意义吗？

Answer 2

复杂度不依赖于嵌套循环的数量

it is O(N^c):
 Time complexity of nested loops is equal to the number of times the
innermost statement is executed.

For example the following sample loops have O(N²) time complexity

for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
   }

   for (int i = n; i > 0; i += c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
   }

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

worst case runtime of the double for loop

algorithm

runtime