可能重复:支持O(1)随机访问和最坏情况下O(1)附加的数据结构?
我曾经在StackOverflow上看到过一个关于证明为最优的“向量”(“数组列表”)数据结构的答案,如果我没记错的话,它会将元素延迟复制到更大的向量上,这样每次向量重新分配时就不会造成巨大的暂停。
我记得它需要O(sqrt(n))的额外空间进行簿记,并且答案链接到了一篇发表的论文,但仅此而已... 我正在极力搜索它(你可以想象搜索“最优向量”之类的内容对我毫无帮助)。
我该在哪里找到这篇论文?
我记得它需要O(sqrt(n))的额外空间进行簿记,并且答案链接到了一篇发表的论文,但仅此而已... 我正在极力搜索它(你可以想象搜索“最优向量”之类的内容对我毫无帮助)。
我该在哪里找到这篇论文?