问使用if-else块的for循环的时间复杂度

EN

不是的。

问题“什么是T(n)?”您所说的是“如果i=n，则O(n^3)，否则O(n^2)”。但问题中没有i，只有n。

想一想类似的问题：“在一周中，Pete周三工作10个小时，每隔一天工作1小时，Pete一周的总工作时间是多少？”你不会真的回答“如果星期是星期三，那么是X，否则是Y”。你的答案必须包括周三和每隔一天的工作时间。

回到你最初的问题，星期三是i=n的情况，所有其他的日子都是i!=n的情况，我们必须把它们加起来才能找到答案。

这是一个关于每个循环执行O(1)的次数的问题。时间复杂度是n的函数，不是i的函数。也就是说，“O(1)在n上执行了多少次？”

当i == n.

• There在所有其他情况下都是
• 的O(n^2)循环的(2n - 2)实例时，O(n)循环有一次运行。

因此，时间复杂度为O((2n - 2) * n + 1 * n^2) = O(3n^2 - 2*n) = O(n^2)。

我已经编写了一个C程序来显示n^2、实际值和n^3的前几个值，以说明它们之间的区别：

#include <stdio.h>

int count(int n){
 int ctr = 0;
 for (int i = 0; i < 2*n; i++){
    if (i == n)
      for (int j = 0; j < i; j++)
         for (int k = 0; k < i; k++)
            ctr++;
    else
      for (int j = 0; j < i; j++)
         ctr++;
 }
 return ctr;
}

int main(){
 for (int i = 1; i <= 20; i++){
  printf(
   "%d\t%d\t%d\t%d\n", 
   i*i, count(i), 3*i*i - 2*i, i*i*i
  );
 }
}

Try it online! (您可以将其粘贴到Excel中以绘制值。)

第一个循环重复2*n次：

for (int i = 0; i < 2*n; i++)
{
    // some code
}

当i == n和时间复杂度为：O(n^2)时，此部分只出现一次

if (i == n)
{
    for (int j = 0; j < i; j++)
        for (int k = 0; k < i; k++)
            O(1)
}

而这一部分则依赖于i。

else
{
    for (int j = 0; j < i; j++)
        O(1)
}

在以下情况下考虑i：

循环重复0次

循环重复1次

循环重复2次

。

。

循环重复n次。(这里的n是2*n)

所以循环重复了(n*(n+1)) / 2次

但是当i == n else部分不工作时，(n*(n+1)) / 2 - n和时间复杂度就是O(n^2)。

现在我们对所有这些部分求和：O(n^2) (first part) + O(n^2) (second part)，因为第一部分只出现一次，所以它不是O(n^3)。

时间复杂度是：O(n^2)。