这个循环的时间复杂度是多少?

What is the time complexity of this loop?

如何确定这个循环的时间复杂度:

for(int i = N-1; i >= 0; i--)
{
    for(int j = 1; j <= i; j++)
    {
        if(numbers[j-1] > numbers[j])
        {
            temp = numbers[j-1];
            numbers[j-1] = numbers[j];
            numbers[j] = temp;
        }
    }
}

您可能已经注意到,这是冒泡排序算法。还有这个算法比较和赋值的频率计数是一样的吗?

对于最好和最坏的情况,您当前实现的复杂度都是 O(n^2),如果仅计算比较、仅计算赋值或两者都相同。

这里是详细的计算,K是一个常数,取决于你想考虑哪些操作的时间复杂度:

如果您想要更高效的冒泡排序算法,请查看 Wiki page or this answer 上的伪代码,您会发现算法的最佳情况复杂度为 O(n)。

计算复杂度

您需要添加正在执行的基本操作/机器指令。 (作为输入大小的函数)

计算

for(int i = N-1; i >= 0; i--)
{          |        |     |
           c1       c2    c3
   for(int j = 1; j <= i; j++)
   {       |        |     |
           c4       c5    c6
      if(numbers[j-1] > numbers[j])--c7
      {
         temp = numbers[j-1];
         numbers[j-1] = numbers[j];
         numbers[j] = temp;
      }
   }
}

c1,c2,c3,c4,c5,c6,c7 是执行与这些构造对应的机器指令的成本(如 i>=0,j<=i 等)

Now for i=N-1 the innerloop is executed N-1 times
    for i=N-2 the innerloop is executed N-2 times
    ....

    for i=0 the innerloop is executed 0 times

所以内循环被执行了 (N-1)+(N-2)+...1+0 次 = N*(N-1)/2

Look carefully the cost is
 = c1+ c2*(N+1) + c3*N+ c4*N+((N*(N-1)/2)+1)*(c5)+ (N(N-1)/2)*(c6+c7);
 = c1+c2+c5+ N*(c2+c3-(c5+c6+c7)/2) + N^2 * (c5/2 + c6/2 + c7/2)
 = c8 + N*c9 + N^2 *(c10)   [c8,c9,c10 are constants]

为什么要将 N+1 与 c2 相乘?那是因为最后一次检查实际上是 i=-1.

现在对于较大的 N 值,N^2 支配 N。 所以时间复杂度是O(N^2)。 所以,T(N)=O(N^2)