algorithm - 这个循环的时间复杂度是多少？

Question

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

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;
        }
    }
}

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

Answer 1

计算复杂度

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

计算

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)