只访问矩阵中的行的时间复杂度

访问我们可以用于循环和时间复杂度的矩阵的所有元素是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

只访问矩阵中的行的时间复杂度

回答

相关问题