具有不同迭代的嵌套循环的大O？

Question

我在确定两组代码示例的Big O运行时间时遇到了一些麻烦,其中迭代依赖于外部循环.我对Big O运行时有一个基本的了解,我可以找出更简单的代码示例的运行时间.我不太确定某些行如何影响运行时间.

我会考虑第一个O(n ^ 2).但是,我不确定.

for(i = 1; i < n; i++){
 for(j = 1000/i; j > 0; j--){  <--Not sure if this is still O(n)
    arr[j]++; /* THIS LINE */
 }
}

我对这个失去了一点点.O(n ^ 3)可能是O(n ^ 2)？

for(i = 0; i < n; i++){
 for(j = i; j < n; j++){
    while( j<n ){
      arr[i] += arr[j]; /* THIS LINE */
      j++;
    }
 }
}

我发现这篇文章并将其应用于第一个代码示例,但我仍然不确定第二个.什么是嵌套循环的Big-O,其中内循环中的迭代次数由外循环的当前迭代确定？

Answer 1

关于第一个.它不是 O(n^2) !!! 为了简单和可读性,让我们以伪代码的形式重写它:

for i in [1, 2, ... n]:                              # outer loop
    for j in [1, 2, ... 1000/i]:                     # inner loop
        do domething with time complexity O(1).      # constant-time operation

现在,内循环内的常量操作次数(取决于i外循环的参数)可表示为:

现在,我们可以计算整体恒定时间操作的数量:

这里N(n)是一个谐波数(见维基百科),这些数字有一个非常有趣的属性:

哪里C是欧拉-马斯刻若尼常数.因此,第一种算法的复杂性是:

关于第二个.似乎代码包含错误,或者它是一个技巧测试问题.代码解析为

for (i = 1; i < n; i++)
    for(j = i; j < n; j++){
        arr[j]++;
        j++;
    }

内循环需要

操作,所以我们可以计算整体复杂性: