確定以下算法的計算複雜度

Question

s = 0 
for i = 1 to n3 
for j = 1 to i do 
s = s + 1 

計算複雜度是什麼意思？

Answer 1

我們假設在這段代碼中的每個操作都需要一定的時間c _i。然後運行時間可以通過總和Ç表達+ C * N3 + C * I * N3 + C * I * N3。我們認爲常數係數不重要，因爲它們只貢獻一個常數值，而不管輸入如何。這給出我們Θ（1）+Θ（n3）+Θ（i * n3 + 1）+Θ（i * n3）。所以在這種情況下，時間複雜度是Θ（n3！），也就是說這個算法在階乘時間內運行。

Answer 2

纔算一些值（多少次S = S + 1我的每次迭代執行和總結），看看你會得到什麼：

1 + 2 + 3 + ... + N = n *（n + 1）/ 2 = n^2/2 + n/2 =>複雜度O（n^2）。