Анализ сложности алгоритмов

Question

Я новичок здесь, так что сокращаю свои слабые места и дайте мне знать, может ли мой вопрос получить какие-либо улучшения.

Так что у меня и с другом есть разногласия по сложности алгоритма. Он, кажется, уверен, что алгоритм имеет большую O-запись O (n^2), но я просто думаю, что его O (n)

Можем ли мы иметь некоторые указатели, мы надеемся, закончим наш аргумент ha!

Алгоритм:

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 

Таким образом, при г = 1, второй цикл выполняется п раз, при г = 2 оно выполняется N-1 раз, и т.д ..

Это дает сумму n + n-1 + n-2 + ... + 1 формуле, дает номер operation() ran is 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