假设存在具有I和J尺寸的2D矩阵。填补这一矩阵具有固定数量可以在两个方式来完成：填充二维数组函数的顺序是什么？

首先，有两个嵌套循环

for (int i=0;i<I;i++) 
{ 
    for (int j=0;j++;j++) 
    { 
     mat[i][j] = 123; 
    } 
}

这是O（N 2）通过书。

谢胜利：带有单环

for(int k=0;k<I*J;k++) 
{ 
    mat[k/I][k % I] = 123; 
}

这是一个为O（n）明显

然而这两种方法采取等于次以通过忽略环变种延迟来执行。

的更重要的标准：双方执行完全相同的时间和顺序

所以我们怎么能说一个是O（N2），另一个是O（N）？

我们可以说这两种方法都是O（n）吗？

来源

2015-09-06 Zich

它看起来就像是我们应该找到谢胜利，一个每增长速度是O（N）根据确定的增长率，但第一个仍然棘手。 – Zich

这是一个为O（n）明显

不。循环的上界是I * J，使得这个O（n^2）。

来源

2015-09-06 15:11:43

好吧，假设我是1，循环就像一个普通的数组（一维），你会认为这是一个o（n2），这个顺序不应该被Data改变。对？ – Zich

是什么让上限变得重要？增长率应该是什么情况呢？ – Zich

如果您正在填充4x4阵列，则在第一种情况下n = 4。4^2 = 16。需要16次迭代才能填充4x4阵列。在第二种情况下，n = 16。这将需要16次迭代来填充数组。

来源

2015-09-06 15:16:19 Todd

那么这两个订单都是一样的？你的回答没有结论！ – Rassam

两者都处理整个数组。似乎这里的每个人都对这个问题感到困惑。这两个都是O（n），因为算法的性能直接关系到数据集的大小。换句话说，你迭代每一个项目一次。我认为这个问题让人们感到困惑，因为它事实上表明，第一个是O（n2）。不是这样。如果学生复制他们的确切作业问题，这样真正的问题就不会在翻译中丢失，这会更容易。我明白他们为什么不这样做。 – Todd

不，你的理解是不正确的。在第二种解决方案中，你假设为'n'实际上是m * n，即O（n^2）。

检查循环变量k = I *∫（m和n在你的例子）

来源

2015-09-06 15:19:52

所以它的一个O（m * n）？和O（k）？我们有这样的事情吗？ – Zich

您可以将您的变量命名为k，爱因斯坦，乌兹别克斯坦或任何其他任何东西，但不会改变任何内容。时间复杂度的大O符号表示什么是顺序，或大致需要多少操作来运行您的算法。O（n^2）表示它将进行m * n次操作（n^2，因为当两者都足够大时，m和n会被比较）。 –

这两种情况下的操作次数是相等的，所以我猜他们都有相同的顺序，但足够大？这是什么意思？但我确信，变量的大小并不重要。 – Zich

填充二维数组函数的顺序是什么？

这是O（N 2）通过书。

这是一个为O​​（n）明显

回答

相关问题

这是一个为O（n）明显