複雜循環

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 ）。