计算嵌套循环的时间复杂度

Question

关于 Big O 时间复杂度分析，我已经坚持了几天的测试中遇到了这个问题：

C代码如下：

   if ( A > B ) {
       for ( i=0; i<n^2/100; i++ ){     //1
           for ( j=n^2; j>i; j-- ){     //2
               A += B;}}
   }
   else {
       for ( i=0; i<2n; i++ ){         //3   
           for ( j=3n; j>i; j-- ){     //4
               A += B;}}
   }

我的第一直觉是这个算法会有一个很大的 O(n²) 和嵌套的 for 循环等等但这不是多项选择答案。试图手动计算每个循环迭代，但无法解释每个内部循环（2 和 4）中 i 的变化。尝试将其写为求和时也遇到了问题。

Answer 1

考虑第一种情况 A > B。对于外循环迭代的 i 的每个值，内循环执行的迭代次数等于 n^2 - i。考虑 n = 2 和 i = 1。 n^2 = 4 并且内部循环迭代 j = 4, j = 3, j = 2，三个迭代，与我们的发现一致。

因此，内循环的总迭代次数是所有 n^2 - i 的总和，其中 i 从 0 到 floor(n^2/100) - 1。让我们定义 k := floor(n^2/100) - 1。那么这个和就等于kn^2 - k(k+1)/2。替换 k 所代表的表达式，我们恢复 [floor(n^2/100) - 1]n^2 - [floor(n^2/100) - 1][floor(n^2/100)]/2。这不大于 (n^2/100 - 1)n^2 - (n^2/100 - 1)(n^2/100)/2。我们可以乘以得到n^4/100 - n^2 - n^4/20000 + n^2/200 = n^4(1/100 - 1/20000) - n^2(1 - 1/200)。由此我们可以看出，第一种情况的时间复杂度是O(n^4)。确实也是Omega(n^4)和Theta(n^4).

在A <= B的情况下，分析类似。很容易证明，第二种情况的时间复杂度是O(n^2)，Omega(n^2)，因此Theta(n^2).

因此，我们可以自信地说：

最坏情况的时间复杂度是O(n^4)；
最好的时间复杂度是Omega(n^2)；
这些边界中的每一个实际上都可以作为 Theta 边界给出。

计算嵌套循环的时间复杂度

Calculating Time Complexity for nested loops

c

big-o

time-complexity

nested-loops