故障與大O估算

Question

我要求給了一些代碼段一大O估計，但我有

int sum = 0; 
for (int i = 0; i < n; i = i + 2) { 
    for (int j = 0; j < 10; j + +) 
     sum = sum + i + j; 

我想的有點麻煩的是，最壞的情況會爲O（n/2），因爲外循環是從i到數組長度n。不過，我不知道，如果內環影響大O.

int sum = 0; 
for (int i = n; i > n/2; i − −) { 
    for (int j = 0; j < n; j + +) 
     sum = sum + i + j; 

對於這一塊，我想這將是爲O（n^2/2），因爲內循環是從j到n和外循環是從n到n/2這給我n *（n/2）

int sum = 0; 
for (int i = n; i > n − 2; i − −) { 
    for (int j = 0; j < n; j+ = 5) 
     sum = sum + i + j; 

我很迷茫在這一個。我的猜測是O（n^2-2/5）

Answer 1

前兩個例子的運行時間是正確的。

對於第一個例子，當然內循環總是執行10次。所以我們可以說總運行時間是O（10n/2）。

對於最後一個例子，外循環只執行兩次，內循環n/5次，所以總運行時間爲O（2n/5）。

需要注意的是，由於大O的複雜性的定義方式，持續性因素和漸近小的方面是可以忽略的，所以你的複雜性可以/應該簡化爲：

• 爲O（n）
• 爲O（n ）
• 爲O（n）

如果你考慮到持續性因素（使用比C大O符號以外的東西可能是~-notation），您可能必須明確構成一個工作單元的構成 - 可能由於有2個附加操作，sum = sum + i + j構成2個工作單元而不是1個工作單元。

Answer 2

你沒有運行嵌套循環：

for (int i = 0; i < n; i = i + 2); 
           ^---- 

這分號終止循環定義，所以i環路剛剛從0開始計數 - > n，步驟2，不做任何事情。 j循環完全獨立於i循環 - 兩者僅依賴於n執行時間。

Answer 3

對於上述算法，最壞情況/最好情況是相同的。
在大O符號的情況下，較低階項和最高階項係數可以忽略，因爲大O用於描述漸近上限。

int sum = 0; 
for (int i = 0; i < n; i = i + 2) { 
    for (int j = 0; j < 10; j + +) 
     sum = sum + i + j; 

外部循環迭代的總數= N/2.對於外環，內環迭代次數=的每次迭代10.so內循環迭代的總數= 10 * N/2 = 5N 。很顯然它是O（n）。 現在考慮休息兩個程序，並自行確定時間複雜性。