算法复杂性分析

Question

我是新来的，所以放松一下，让我知道我的问题是否有任何改进。

所以我和一个朋友在算法的复杂性上有点分歧。他似乎确信该算法有一个O（n^2）的大O符号，但我只是认为它的O（n）

我们能有一些建议吗，希望能结束我们的争论哈！

算法：

Input: Matrix M[1..n][1..n]
Output: boolean true if M is lower triangular
begin isLowerTriangular(Matrix[][] M, size n)
    for i:=1 to n-1 loop
        for j:=i+1 to n loop
            if M[i][j] != 0
            return false
     return true
end isLowerTriangular

Answer 1

它是O（n^2）。

for i:=1 to n-1 loop
    for j:=i+1 to n loop
        operation()
    done
done

因此，对于i=1，第二个循环执行n次，对于i=2，执行n-1次，等等

这给出了总和n + n-1 + n-2 + ... + 1给出运行的CCD_ 2个数的公式是n*(n+1)/2或(n^2 + n)/2。

因此，它是O（n^2）

编辑：

获取公式

得到结果的诀窍是加上我所说的逆和，也就是按相反顺序的相同和。以下是它的工作原理：

We want to compute 1 + 2 + 3 + ... + n-2 + n-1 + n
For this, we add n + n-1 + n-2 + ... + 3 + 2 + 1
(we remember that we have to divide by two after).
We pair the operands of those two sums now:
   1  +  2  +  3  + ... + n-2 + n-1 +  n
+  n  + n-1 + n-2 + ... +  3  +  2  +  1
= n+1 + n+1 + n+1 + ... + n+1 + n+1 + n+1
= n * n+1
To get this, we just added together 1 and n, then 2 and n-1, ...
Remember that we have to divide by 2, and we get the final result:
1 + 2 + 3 + ... + n-2 + n-1 + n = (n * n+1)/2