algorithm - while 循环的复杂度是多少？

Question

我有下面的代码。在哪里，我必须以之字形方式打印矩阵

arr3 = [
[1,    2,   3,   4],
[5,    6,   7,   8],
['a', 'b', 'c', 'd'],
['X', 'Y', 'Z', 'N']
]

def zigZagMatrix(arr, n, m):
    i_prev = 0
    j_prev = 0
    i = 0
    j = 0
    done = False
    while not done:
        while i >= 0 and j < m:
            print(arr[i][j])
            i -= 1
            j += 1

        if i == n-1 and j > m-1:
            done = True

        i_prev += 1
        if i < n-1 and i_prev < n:
            j = 0
        else:
            j_prev += 1
            j = j_prev
        if i_prev >= n:
            i = n - 1
        else:
            i = i_prev


zigZagMatrix(arr3, 4, 4)

对我来说它看起来像 O(n)，因为我们必须遍历整个数组，但是还有另一个 while 循环 确实运行 直到条件失败。所以，我真的很困惑。是 O(n) 还是 O(n) + O(m) 还是其他

Answer 1

假设代码是正确的并且矩阵的每个元素都打印一次，那么双 while 循环的复杂度就是打印的元素数。因为你有一个 n×m 矩阵，所以你有 n×m 个元素要打印。这意味着复杂度为 O(n×m)。

但是，我已经测试了代码，它似乎从未达到停止条件。该程序一直在不断迭代。这意味着，在其当前版本中，复杂性未定义。如果有的话，那将是无限的。