2

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

4

2 回答 2

2

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

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

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

于 2012-12-14T00:04:39.293 回答
1

这取决于它的含义N

  • 如果N是方阵的行数和列数,则复杂度为O(N^2)
  • 如果N是矩阵中元素的总数(即N = R*CRC数, 是列数),那么复杂度是O(N)
于 2012-12-13T16:54:27.793 回答