Matrix_in_spiral_order(矩阵)的空间和时间复杂度

Question

我正在阅读Python (Aziz，Lee，Prakash)编程面试的元素，并不理解他们的算法在空间和时间上的复杂性。要求以螺旋顺序返回矩阵的问题(例如here)。

在算法的最后，作者指出这是O(n^2)的时间复杂度和O(1)的空间复杂度。我正式研究复杂性已经有几年了，所以我对这两种说法都不理解。在下面的代码中，我们构建了一个全新的数组，所有元素都是螺旋排列的，这会让我相信这不是一个就地操作，因此空间复杂度为O(nxn)。

对于时间复杂性，我也感到困惑。对于每个元素，我们只迭代一次二维数组。因此，它不会被认为是O(n)吗？这与仅仅将其展平为一维数组并遍历一次有何不同？

def matrix_in_spiral_order(square_matrix):
    SHIFT = ((0,1),(1,0),(0,-1),(-1,0))
    direction = x = y = 0
    spiral_ordering = []

    for _ in range(len(square_matrix)**2):
        spiral_ordering.append(square_matrix[x][y])
        square_matrix[x][y] = 0
        next_x,next_y = x + SHIFT[direction][0], y+ SHIFT[direction][1]
        if (next_x not in range(len(square_matrix)) or next_y not in range(
              len(square_matrix)) or square_matrix[next_x][next_y] == 0):
            direction = (direction +1) & 3
            next_x, next_y = x+ SHIFT[direction][0], y + SHIFT[direction][1]
        x,y = next_x, next_y
    return spiral_ordering

我最终使用不同的解决方案递归地解决了这个问题，但仍然想了解他们是如何得出上述算法的分析的。

Answer 1

他们对N的定义是矩阵边的长度，而你对N的定义是矩阵边的乘积。这看起来像是六个，六个另一个，尽管它是开放的争论，以减少误导性。

至于空间复杂性，再一次，听起来他们的解释是返回的结果不算数。这是公平的，但它确实需要明确，我认为你的直觉到目前为止表达了他们的两个主张的怀疑是合理的。

顺便说一句，我同意@Blorgbeard的观点，即他们提供的算法不够典范。