python - matrix_in_spiral_order(matrix) 的空间和时间复杂度

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 的观点，即他们提供的算法不够典范。