アルゴリズムの複雑さの分析

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 にどの式を与えますの実行回数がn*(n+1)/2または(n^2 + n)/2であることを示します。

したがって、それだはO（n^2）

EDIT：

結果を取得するためのトリックは、私が逆の合計呼ん追加することで式に

を取得し、それがあります逆順で同じ合計。ここではそれがどのように動作するかです：

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