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²)。