Space 和 matrix_in_spiral_order（矩阵）的时间复杂度

Question

我正在阅读 Python（Aziz、Lee、Prakash）中的编程基础访谈，但不了解其中一种算法的 space 和时间复杂度。该问题要求 return 螺旋顺序的矩阵（示例 here）。

在算法的最后，作者声明这是 O(n^2) 时间复杂度和 O(1) space 复杂度。自从我正式研究复杂性以来已经有几年了，所以我不理解这些说法中的任何一个。在下面的代码中，我们构建了一个全新的数组，其中所有元素都按螺旋顺序排列，这会让我相信这不是一个就地操作，因此会有 space 的 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的定义是矩阵边的乘积。这看起来像是一个中的六个，另一个中的六个，尽管对于哪个误导性较小尚有争议。

至于 space 的复杂性，再一次，听起来他们的解释是返回的结果不算数。这很公平，但确实需要明确说明，我认为就对他们的两个主张表示怀疑而言，你的直觉是合理的。

附带说明一下，我同意@Blorgbeard 的观点，即他们提供的算法不够典范。

Space 和 matrix_in_spiral_order（矩阵）的时间复杂度

Space and Time complexity of matrix_in_spiral_order(matrix)

python

complexity-theory

list

time-complexity