使用O(1)性能初始化n个元素数组？

Question

有人知道我该怎么做？

谢谢

Answer 1

如果您需要对一组n元素的每个元素执行某些操作,则不能以比O(n)性能更好的方式执行此操作.

Answer 2

如果你的意思是“在与N无关的时间内初始化N个项目的密集数组”，那么这在物理上是不可能的。密集数组的存储空间随着项目数量线性增长，并且初始化该空间需要线性时间。

您可以使用稀疏数组进行常量时间初始化。这本质上是一个关联数组（或哈希图、字典或表，具体取决于语言），它在第一次访问项目时对其进行初始化。