Trie
。向量被实现为一个 Trie
数据结构。请参见 http://en.wikipedia.org/wiki/Trie。另一个角度来看:我们正在谈论的不是log(2,N),而是log(32,N)。如果你尝试绘制它,你会发现它几乎是一条水平线。因此从实用的角度来说,随着集合的增长,处理时间的增加将很难被察觉。
是的,这仍然不是真正的常数(这就是为什么它标记为“eC”而不仅仅是“C”),在较短的向量周围你将能够看到差异(但再次说明,由于操作数量增长缓慢,这种差异非常小)。
log(32,N)
,因此复杂度应该是 O(logN)
而不是 eC
,对吧? - Lai Yu-Hsuan为什么要这样呢?简单:为了性能。
与为每个单独的数据元素分配数千/数百万/数十亿次内存分配不同,内存是以32个元素块为单位分配的。与直接查找数据时要向下遍历很深的树相比,该结构非常浅——是一棵非常宽、短的树。例如,深度为5的树可以包含32^5个数据元素(对于4字节元素=132GB,即相当大),每个数据访问将从根节点查找并遍历5个节点(而大型数组将使用单个数据访问)。向量不会主动为所有n级(数据)分配内存,而是按需要以32个元素块为单位分配。它提供了类似于巨大数组的读取性能,同时具有类似于二叉树的功能特性(功率、灵活性和内存效率)。
:)
以下内容可能对您有所帮助: