使用for循环迭代2D数组的时间复杂度是多少？
在this answer中，它说：
算法如果其执行时间与输入大小成正比，即时间随着输入大小的增加而线性增长，则称为线性时间。
我输入了一个3x3 array.So，我需要输入9 numbers.It，需要9次迭代。
我输入了一个4x4 array.So，我需要输入16 numbers.It，需要16次迭代。
.
迭代的执行与数字的数量(或大小)成正比。所以我认为时间复杂性应该是O(n)。
但是another answer说：
O(n^c)：嵌套循环的时间复杂度等于执行最内部语句的次数。例如，以下示例循环具有O(n^2)时间复杂度
for (int i = 1; i <=n; i += c) {
for (int j = 1; j <=n; j += c) {
// some O(1) expressions
}
}我觉得有点困惑。因此，我认为问题也可以是：
n在数组中的含义是什么？(它是指数组的大小还是数组的维数？)使用for循环迭代2D数组的时间复杂度是多少？是O(n)还是O(n^2)？
如果时间复杂度是O(n^2)，则由于它有两个for循环。我使用它来创建一个3x3数组：
a[0,1,2] -> b[0,1,2] -> c[0,1,2]所以我用它来迭代这个arrays.It将是O(n)，所以它比使用for循环迭代arrays.Why更快？
PS:我用Google翻译看到了这些答案，所以我可能误解了。。
回答 4
Stack Overflow用户
发布于 2020-03-25 09:59:17
数组中n的平均值是多少？(它是指数组的大小还是数组的维数？)循环迭代2D数组的时间复杂度是多少？是O(n)还是O(n^2)？
你是完全正确的。这是惯例的问题。在特定的问题中，n所指的是什么是很重要的。
如果我们的数组是arr[n][n]，迭代需要O(n^2)时间。如果我们的数组是arr[k][k]，而n=k*k是数组的大小，迭代需要O(n)时间。这里没有矛盾，因为在这些情况下，我们对n的定义是不同的。
通常，如果只访问一次数组元素，就会被认为具有线性复杂性。无论您如何用O表示法来表达这一点。
Stack Overflow用户
发布于 2020-03-25 09:52:51
嵌套的for循环的复杂度确实是n^2，而不是n，数组中的n是大小。
也许需要考虑一些可以帮助您的事情:考虑是否需要以类似的方式迭代两个不同的数组，并且数组有不同的m和n的大小。
for (int i = 1; i <=n; i += c) {
for (int j = 1; j <=m; j += c) {
// some O(1) expressions
}
}这将是O(m*n)。你要问的是这个问题的专门化。
Stack Overflow用户
发布于 2020-03-25 09:57:38
对于4x42D数组操作，如果您的输入仅为4，则它将具有指数复杂性。如果你输入的是所有16个数字，那么它是线性的。这一切都取决于你通过的是什么。
在您的示例中，如果n是您的输入大小，那么嵌套迭代的事实使它成为O(n^2)。
https://stackoverflow.com/questions/60846315
复制相似问题
腾讯云开发者
