只訪問矩陣中的行的時間複雜度

訪問我們可以用於循環和時間複雜度的矩陣的所有元素是O(n^2)。但是，當我們只訪問2D數組中的行時，時間複雜度是多少？當n =行數時是O(n)？例如： -只訪問矩陣中的行的時間複雜度

int arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; 
for (int i = 0; i < arr.length; i++) 
    for (int j = 0; j < arr[0].length; j++)

的時間爲上述行復雜度爲O(n^2)。

但是，如果我們訪問矩陣以下面的方式將時間複雜度仍然是O(n^2)還是會O(n)

for (int rows[] : arr) - Time complexity is O(n) or O(n^2)

來源

2017-06-07 Newbie

這個循環只會運行'rows'次所以除非你做了一些複雜的操作，它是'O（rows）'。假設'rows = cols'，它是'o（n）' –

我想把它作爲[Big O，你如何計算/近似它？]的副本來關閉它（https://stackoverflow.com/questions/3255/）你正試圖在代碼中看到與計算大O的方式相沖突的東西。唯一的例外將是一種使用對象的深層副本的語言在for-each循環中，我不確定哪怕存在（Java絕對不會這樣做）。 – Dukeling

如果你要遍歷的每一行的所有單元格，所以它仍然爲O （N^2）。在考慮運行時間時，這兩種方法之間沒有實際的區別。

來源

2017-06-07 09:52:16 LiorP

int arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; 
for (int i = 0; i < arr.length; i++) 
    for (int j = 0; j < arr[0].length; j++)

這是複雜的O（n）而不是O（n^2）。那就是你只能遍歷n個項目，而當n增加時它會線性增加。

來源

2017-07-06 18:39:48

只訪問矩陣中的行的時間複雜度

回答

相關問題