這種最壞情況分析是否正確？

下面是代碼：這種最壞情況分析是否正確？

int Outcome = 0; 
for (int i = 0; i < N; i++) 
    for (int j = i+2; j = 0; j--) 
     Outcome += i*j;

這裏是我的分析。由於第一行是賦值語句，因此這需要一個時間單位O（1）。第2行的分解爲：1 + N + N = 2N + 2.由於循環的內容是單個操作，所以第3行循環及其塊執行i + 1操作。這也是一個嵌套的for循環。最後，第4行需要執行一個時間單位。因此，用N代表的這個代碼的大哦表示是O（N ）。

來源

2013-05-25 user2421270

聽起來對我來說是正確的。做得好！ –

'x^2'是二次方程，它是在階數'2'的'x'上的多項式。你可以說你的複雜性是'O（i * j）'和'j = O（i）'，因此你有'O（n^2）'......每當你有一個嵌套循環時，它通常是'O n^2）':) – Bill

請參閱CS上的[此依賴嵌套循環複雜性]（http://cs.stackexchange.com/questions/4590/big-o-nested-for-loop-with-dependence）問題。 – user2246674

確切地說：正如你所說，第4行是1操作。對於特定的i，執行內部循環i+3次。因此，您的總體操作數量爲

sum(0 <= i <= N-1 : i+3) 
    = 3N + sum(0 <= i <= N-1 : i) 
    = 3N + N(N-1)/2 
    = N^2/2 + 5N/2 
    = O(N^2)

來源

2013-05-25 23:17:54

您的直覺對於最終效率等級是正確的，但它可以更嚴格。首先，您通常會選擇最昂貴的基本操作來計算您的分析。在這種情況下，它可能是最內層循環中的乘法，每次迭代都會執行一次。那麼它被稱爲多少次？在最外層循環的第一次迭代中，內循環將迭代兩次。在第二次外迭代時，它將是三次，並且類似地達到N + 2（我假設內部環路條件意味着是j >= 0）。所以這給我們留下了以下總結：

sum(2, 3, 4, 5, 6 ..., N+2) 
= sum(1, 2, 3, 4 ..., N+2) - 1 
= (N+2)(N+3)/2 - 1

這是O（N²）（實際上是因爲你有這個特定的結果，將永遠是你可以說這是在Θ（N²）相同）。

來源

2013-05-25 23:23:43 tsherif

複雜度等級* –

這種最壞情況分析是否正確？

回答

相關問題