algorithm - 初始化二维矩阵的时间复杂度是多少？

Question

我想将矩阵初始化为所有 0 值。复杂度是 O(1) 还是 O(n)？

Answer 1

事实上，如果初始化复杂度是一个问题，并且进一步的矩阵访问是有序的，你可以：

1. 有一个额外的数据结构来跟踪什么矩阵元素（行或列甚至单元格）被初始化；
2. 仅在您访问它们时才延迟初始化元素。

这种方法在矩阵初始化中可能不会比在进一步处理中更复杂。

Answer 2

这取决于它的含义N

• 如果N是方阵的行数和列数，则复杂度为O(N^2)
• 如果N是矩阵中元素的总数（即N = R*C是R行C数， 是列数），那么复杂度是O(N)。