相关疑难解决方法(0)

在讨论算法的时间复杂度时,"恒定摊还时间"是什么意思？

这是最近一次采访问题.请设计一个具有插入,删除,随机的数据结构o(1)时间复杂度,数据结构可以是数组等基本数据结构,可以是基本数据结构的修改,也可以是基本数据的组合结构.

我正在寻找Eric Lippert提出的这样的解决方案。这是一个很好的实现，因为它是不可变的，附加时间为O(1)，但缺点是O(i)随机访问时间。

另一方面，有一个很好的实现集合的方法，O(1)它具有追加访问和随机访问两种功能。唯一的问题是它强烈依赖于可变性。

我的问题是如何实现将两种解决方案的优点结合在一起的集合？那是：

1. 不变性
2. O(1) 追加时间
3. O(1) 随机访问时间

内存复杂性对我来说不是什么大问题。