螺旋遍历二维矩阵的时间复杂度？

Question

我正在学习如何螺旋遍历二维矩阵，我遇到了以下算法：

def spiralOrder(self, matrix):

    result = []

    while matrix:
        result.extend(matrix.pop(0))
        matrix = zip(*matrix)[::-1]

    return result

我现在很难弄清楚这个问题的时间复杂性，因为zip函数在while循环中。你知道吗

如果有人能帮我解释一下时间复杂性，我将不胜感激。你知道吗

谢谢你！你知道吗

Answer 1

这个问题的已知时间复杂度是一个常数O（MxN），其中M是MxN矩阵中的行数，N是列数。这是一个很棒的算法，但看起来可能会慢一些。你知道吗

仔细观察，循环的每一次迭代都会经历以下操作：

pop() # O(1)
extend() # O(k) where k is the number of elements added that operation
*matrix # O(1) -> python optimizes unpacking for native lists
list(zip()) # O(j) -> python 2.7 constructs the list automatically and python 3 requires the list construction to run
[::-1] # O(j/2) -> reverse sort divided by two because zip halved the items

不管有多少次循环迭代，当这完成时，您将至少调用结果.extend在矩阵中的每个元素（MxN元素）上。所以最好的情况是O（MxN）。你知道吗

我不太确定的是重复的拉链和列表反转增加了多少时间。循环只被大约M+N-1次调用，但是压缩/反转是在（M-1）*N个元素上完成的，然后在（M-1）*（N-1）个元素上完成，依此类推。我最好的猜测是，这种函数至少是对数的，所以我猜总体时间复杂度大约在O（mxnlog（MxN））左右。你知道吗

https://wiki.python.org/moin/TimeComplexity

Answer 2

不管你如何遍历一个二维矩阵，时间复杂度在维度上总是二次的。你知道吗

因此，一个m×n矩阵需要O（mn）时间来遍历，而不管它是螺旋矩阵还是行主矩阵。你知道吗