arrays - 二维数组中的算法复杂度

Question

假设我有一个包含 n*m 个元素的数组 M，所以如果我想打印它的元素，我可以这样做:

for i=1 to m
    for j=1 to n
       print m[i,j]
    next j
next i

我知道打印指令是在常数时间内完成的，所以在这种情况下，我的算法复杂度为:

\sum_{i=1}^{m}\sum_{j=1}^{n}c=m.n.c

所以我想是 O(n) 的顺序

但是如果数组的行数和列数相同，我想复杂度是:

\sum_{i=1}^{n}\sum_{j=1}^{n}c=n.n.c

所以它的阶数为 O(n^{2})

我的假设是否正确？

Answer 1

我假设 m 和 n 是变量而不是常量。在那种情况下，算法的运行时间应该是 O(mn)，而不是 O(n)，因为运行时间与数组中的元素数量成正比。您通过求和得出了这一点，但通过查看每个数组元素完成了多少工作可能更容易看出。鉴于此，您是正确的，如果 m = n，则运行时间是 n 的二次方。

希望这对您有所帮助!