如何計算算法的複雜度？

Question

我目前正在介紹算法課程，我需要幫助解決這個問題。由於我對此表示懷疑，因此不太確定。 :)我有兩個問題：

問題1： 從我所瞭解的算法書中，我相信這個問題的運行時複雜度是f（n）= 3n。爲什麼？那麼因爲while循環將繼續運行n次，並且對於循環的每次迭代，您有3次操作（1次減法，1次乘法和1次加法）是我的過程是正確還是錯誤？由於賦值語句，它應該是f（n）= 5n。我知道兩者都是相同的複雜性，但我真的很想明確地確定。

問題2： 至於說明算法是否找到了多項式的值，我已經足夠讓我舉一個例子來找到一個特定多項式的值，例如3n^2 + 2n + 1來證明該算法的工作原理還是有更好的方法來做到這一點。

Answer 1

對於第一個問題，複雜度確實是O（n）。

如果你想要更確切地確定你想要的東西，在每個循環中，你的算法將需要一定的操作量（我的複雜課程有點舊，我希望我不會錯過任何; ））：

1. 判斷循環條件：ⅰ> = 0
2. 計算x和y的乘積
3. 結果添加到A [1]
4. 將結果存儲在y中
5. 計算我 - 1
6. 。結果存儲在我

你的計劃也將做3個額外的操作：

1. Y = 0
2. 我= N
3. 比較我到0的最後一次，不進入循環

你也可以考慮計算機必須爲y和i等分配內存的事實。

對於第二個問題，如同在數學中一樣，證明它在一種情況下是有效的，並不足以證明它在任何情況下都有效。

爲了證明你的算法，你首先必須編寫你的前提條件（你應該有什麼入口）。 然後，你必須在你的while循環開始時指出你的程序應該處於的狀態，並且在它的結尾處同樣。

例如： Y = 0 i = N時 而（ⅰ> = 0）{// Y =總和（A [j]的+ X ^，j將>ⅰ） Y = A [1 ] + x^i //我假設它是x^i而不是x * y y = Sum（a [j] + x^j，j> i-1） i = i-1 // y = Sum（a [j] + x^j，j> i） }

我沒有找到任何必要的程序前提條件，我剛纔提到過它，因爲重要的是要考慮它其他類似的作品。 如圖所示，這個想法是在每個點顯示程序的狀態，所以我們知道它到達最後的狀態。