下面的僞代碼的時間複雜度是多少？

Question

XYZ(a, b, c, m, n){ 

For p = 1 to m do 
    For q=p to n do 
     c[p,q] = a[p,q] + b[p,q];} 

我認爲是N + N-1 + N-2 + ... +（N-M + 1）。但我不確定。它是這個還是m * n？

Answer 1

讓我們簡化代碼：

For p from 1 to m 
    For q from p to n 
     Do something 

假設Do something部分在固定時間內完成的，什麼決定了代碼的時間複雜度是兩個循環。外循環運行m次，而內循環運行n-p，p從1變爲m。

如果m >= n，Do something部分重複n+(n-1)+...+1 = n*(n+1)/2 = n²/2 + n/2 = O(n²)次。

否則，如果n > m，它的重複n+(n-1)+...+(n-m+1) = (n*(n+1) - (n-m)*(n-m+1))/2 = 1/2 * (n² + n - n² + 2*n*m - n - m² + m) = O(2*n*m - m²) = O(n²)倍。

無論如何，O(n²)是一個正確的答案，但如果n >> m，更確切的答案是O(n*m)。