分析算法的時間複雜性

Question

我正在分析一個算法，我只想知道我是否在正確的軌道上。

對於這種算法，我只計算在其中有***的線上的乘法。

這裏的算法：

1. 所以我從最內部行開始，我可以看到有2個操作存在（這兩個乘法）。
2. 現在我正在看最內部的2個循環，所以我可以告訴p=p*20*z正好執行(j) + (j-1)+(j-2)+(j-3)...1次。這恰好等於j(j+1)/2。
3. 總而言之，由於有兩個乘法，所以發生了2 * (j(j+1)/2)。
4. 最後，「i」循環正好發生n次，所以總共是n(2 * (n(n+1)/2))。

這是我背後的思考過程。我對麼？謝謝。

Answer 1

您的思考過程是正確的。你需要用n代替j項（n是j可以假定的最大值），但這可能是一個錯字。

此外，您可以從您所在的位置進一步簡化：

n(2*(n(n+1)/2)) 
2*n*(n^2+n)/2 
n^3+n^2 

=> O(n^3) 

的最後一步是因爲N的立方內將在一個更大的速度比n平方項，我們可以說，這將主導增長大n的運行時。除此之外，我還要提到的是，您應該考慮將商店作爲操作以及兩次乘法，儘管顯然這不會改變簡化的大操作系統。

Answer 2

計算在這個特殊的例子可以簡化，如果你能找到所有的三個環路具有相同的退出條件up to n：

1. i <= n
2. j <= n
3. k <= j

基本上第三個循環也會運行n迭代，因爲j <= n所以k <= n， 這意味着複雜性將是n * n * n = O(n^3)

Answer 3

這就是你如何獲得你的算法有條不紊的發展順序：