解释此解决方案生成零矩阵的时间和 space 复杂度

Question

以下是对以下提示的回答：

编写一个算法，如果 M x N 矩阵中的元素为 0，则其整个列和行都设置为零。

仅供参考：我发现还有更多最优解；我想知道 this 答案的时间和 space 复杂度。

如果我错了请纠正我，但我的理解是粗略的时间复杂度是 O(MN + K(N + M)) 其中 k 是列表的长度迭代通过的零位置元组。但是 K 永远小于 N * M，那么这是否可以分解为忽略 K？还是我在这里完全偏离了基地？

我不确定 space。我知道元组占用的内存比列表少，但这有关系吗？会是 O(MN) 吗？

def zero_matrix(matrix):
    if not matrix: return matrix

    zero_elem = []
    for (i,row) in enumerate(matrix):
        for (j,num) in enumerate(row):
            if num == 0: zero_elem.append((i,j))

    if not zero_elem or len(zero_elem) == len(matrix) * len(matrix[0]): 
        return matrix

    for (row, col) in zero_elem:
        matrix[row] = [0 for num in matrix[row]]
        for row in matrix:
            row[col] = 0

    return matrix

提前致谢！

Answer 1

I know that tuples take up less memory than lists, but does it matter?

不适用于大 O 表示法。它们都是线性内存（如果我理解正确的话）所以复杂度不受此影响。

您的 zero_elem 列表将具有 O(MN) 内存，因为它最多具有 MN 个恒定长度的元组。

至于你的时间复杂度，你是在正确的轨道上。但是，完整的运行时间将是 O(MN(N+M))，因为您的矩阵可能只是全零（或顺序 MN 零），这将需要您迭代每一行和每一列顺序 MN 次。

如果您想要更优化的解决方案，这可以在 O(MN) 时间和 O(M+N) space 内轻松完成。您可能会推送一个 O(1) 内存，但我看不出有任何理由这样做。

解释此解决方案生成零矩阵的时间和 space 复杂度

Explain the time and space complexity in this solution to generating zero matrix

python

big-o

tuples

time-complexity

python-3.x