说明在此解决方案中生成零矩阵的时间和空间复杂性

Question

以下是对以下提示的回答：编写算法，如果M x N矩阵中的元素为0，则其整个列和行都设置为零。FYI：我意识到还有更多的最佳解决方案。我想知道this答案的时间和空间复杂度是多少。如果我错了，请纠正我，但我的理解是，这的粗略时间复杂度是O（MN + K（N + M）），其中k是得到的零位置元组列表的长度遍历。但是K总是小于N * M，因此可以将其分解以忽略K吗？还是我完全不在这里基地？我不确定空间。我知道元组占用的内存比列表少，但这有关系吗？是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

我知道元组占用的内存少于列表，但这有关系吗？

不是Big-O表示法。它们都是线性内存（如果我理解正确的话），因此复杂度不受此影响。

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

关于您的时间复杂度，您处于正确的轨道上。但是，由于您的矩阵可能完全是全零（或MN的零阶），所以完整的运行时间将是O（MN（N + M）），这将需要您遍历每行和列的MN次。

如果您需要更优化的解决方案，则可以在O（MN）时间和O（M + N）空间中轻松完成此操作。您可能可以压入O（1）内存，但我没有任何理由这样做。