算法複雜性分析

我在這裏是新來的，所以削減我的一些鬆懈，讓我知道如果我的問題可以有任何改進。算法複雜性分析

所以我和一位朋友對算法的複雜性有點不同意。他似乎確定該算法有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

來源

2016-05-17 user3667111

這是O（n^2）導致迭代的總NUMER約爲'N *（N-1）/ 2' –

沒有，如何將遍歷只有一次？它將迭代到'n'。所以如果'i + 1 = 2'和'n = 100'它會迭代98次 –

這是爲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 的公式，其給出operation()的編號是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

來源

2016-05-17 23:30:27

爲什麼你給出了給出前面結果的公式？ – user3667111

感謝您指出錯誤，我編輯了帖子並忘記更新一個部分。 –

那麼你如何從n + n-1 + n-2得到n *（n + 1）/ 2？ – user3667111

算法複雜性分析

回答

相關問題