以下伪代码的时间复杂度是多少？

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

What is the time complexity of the following pseudocode?