algorithm - 两个叠瓦环的复杂性

Question

我有这个算法(为了方便起见，用c代码):

int algo(int *T, int size)
{
   int n = 0;

   for (int i = 1; i < size; i++) {
       for (int j = i; j < size; j++) {
           n += (T[i] * T[j]);
       }
   }

   return n;
}

该算法的时间复杂度是多少？

我打赌它是n * log (n)，因为我们对size长度进行了两次叠瓦式迭代，一次对size - i 第二次，但我不确定。

欢迎提供复杂性的正式证明!

Answer 1

这是一个 O(N²) 算法。

• 外循环的第一次迭代运行 N-1 次
• 外循环的第二次迭代运行 N-2 次
• 外循环的第三次迭代运行 N-3 次
• ...
• 外循环的最后一次迭代运行了 1 次

总次数为(N)+(N-1)+(N-2)+...+1，即sum of arithmetic progression 。计算总和的公式为 N*(N-1)/2，即 O(N²)。