用大O計算時間複雜度

我有一個任務，我不確定;我要計算下面的代碼的時間複雜度：用大O計算時間複雜度

int a[][] = new int[m][n];  //O(1) 
int w = 0;      //O(1) 
for (int i = 0; i < m; i++)  //O(n) 
    for (int j = 0; j <n; j++) //O(n) 
     if (a[i] [j] % 2 == 0) //O(logn) 
     w++;      //O(1)

從我Ø估計

所以我把它們加起來：

O（1）+ O（1）+ O（N）*（O （n）*（O（logn）+ O（1）/ 2）
O（1）+ O（1）+ O（n）*（O（nlogn）+ O（n）/ 2）
O（1）+ O（1）+（O（N 2 logn）時間+ O（N 2 ）/ 2）
= O（N 2 logn）時間

我不確定我的思路是否正確，有人可以幫忙嗎？

來源

2016-10-05 RVER12321312

該日誌是錯誤的。完整的複雜性只是二次的。（假設模數不變，if就是一個常量運算） – sascha

@sascha它不是二次的。 – xenteros

@sascha哦，我明白了......我在筆記裏的某個地方講過我的講師，因爲變量有可能是％2，並且出於某種原因它是o（logn）。由於 – RVER12321312

for (int i = 0; i < m; i++)  //O(m) 
    for (int j = 0; j <n; j++) //O(n) 
     if (a[i] [j] % 2 == 0) //O(1) 
     w++;      //O(1)

所以在big-o方面總的複雜性：

O(m)*(O(n) + O(1) + O(1)) = O(m)*O(n) = O(m*n)。

來源

2016-10-05 15:06:32 xenteros

您正在向橙子添加蘋果。你不能告訴'int a [] [] = new int [m] [n];'是'O（1）'而'for（int i = 0; i zerkms

@zerkms我同意。它是'O（mn）'。沒有考慮初始化。 – xenteros

不僅如此 - 我的觀點是你不能簡單地將'O（）'近似值加在一起。簡單的理由：你爲什麼假設'new int [m] [n]'是固定時間？ – zerkms

for (int i = 0; i < m; i++) //O(m) 
    { 
    for (int j = 0; j <n; j++) //O(n) 
    { 
     // your code 
    } 
    }

所以i循環會繼續m次，而j循環會運行n次。所以總的代碼將繼續m*n時間，這將是它的時間複雜度：O(m.n)

來源

2016-10-05 15:01:25

所以o（m）和o（n）變量應該被獨立處理，而不是o（n^2）來運行for循環兩次？ – RVER12321312

如果for循環運行兩次（每次最多n次），則會有兩個獨立的O（n）計算（考慮它是一個循環內的循環）。 O（n）爲外環，O（n）爲內環，導致O（n^2）。 –

但是，如果它是兩個單獨的for循環，每個運行到n，那麼它將是O（n）+ O（n）= O（2n），這與O（n）相同 –

-1

最終的複雜度爲O（N^2）

你的邏輯是，除了關閉...

int a[][] = new int[m][n];  //O(1) 
int w = 0;      //O(1) 
for (int i = 0; i < m; i++)  //O(n) 
    for (int j = 0; j <n; j++) //O(n) 
     if (a[i] [j] % 2 == 0) //O(1) 
     w++;      //O(1)

嵌入在第二個for循環中的if語句只是簡單地引用數組中的元素並進行基本比較。這是時間複雜度O（1）。此外，通常您不會考慮在時間複雜性問題中初始化變量。

來源

2016-10-05 15:04:22 PrestonM

錯誤！第一個循環直到m，而不是n！ –

@ValentinMontmirail它是相同的功能類。 – sascha

這個答案錯了嗎？ http://stackoverflow.com/questions/362059/what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop – PrestonM

用大O計算時間複雜度

回答

相關問題