我理解“恒定时间复杂度O（1）”，但当我遇到有效的恒定时间复杂度这个术语时，我非常困惑 . 我从Scala厨师书中得到了关于有效恒定时间的句子 .
操作有效地持续时间，但这可能取决于某些假设，例如向量的最大长度或散列键的分布 .
但我认为上面的例子并不是有效的恒定时间，而是Amortize恒定时间 .
请你明确区分恒定时间和有效恒定时间 . 这将非常有帮助 . 谢谢!!
这几乎与报价所说的完全相同：它不是恒定的时间，但是，在一些合理的假设下，它只是比常数时间略差，不足以引起注意 .
所以，它不是恒定的时间，但它是如此接近以至于差异无关紧要，这有效地使它（几乎）保持恒定的时间，
例如，将数组数据结构实现为32路树技术上使其成为O（log n）而不是O（1） . 但是一个包含40亿个条目的数组只有6.4级深度，所以它基本上比传统的可变连续数组慢7倍 .
1 回答
这几乎与报价所说的完全相同：它不是恒定的时间，但是，在一些合理的假设下，它只是比常数时间略差，不足以引起注意 .
所以，它不是恒定的时间，但它是如此接近以至于差异无关紧要，这有效地使它（几乎）保持恒定的时间，
例如，将数组数据结构实现为32路树技术上使其成为O（log n）而不是O（1） . 但是一个包含40亿个条目的数组只有6.4级深度，所以它基本上比传统的可变连续数组慢7倍 .