我正在阅读this sqlite documentation，并在他们的有序查找中看到了这段话：
由于信息是按rowid顺序存储在表中的，SQLite可以使用二进制搜索找到正确的行。如果表包含N个元素，查找所需行所需的时间与logN成正比，而不是像全表扫描中那样与N成正比。如果表包含1000万个元素，这意味着查询速度将达到N/logN或大约快100万倍。
我以前从未见过N/logN复杂度。为什么它是N/logN而不是logN查找？粗略的搜索说它是从数组中的bucketed有序段开始的。是因为内存限制了二进制搜索段的大小，而数据集足够大吗？
如果是，N/logN是如何计算的？是否有其他真实世界的应用程序使用N/logN复杂度？
1条答案
按热度按时间lvmkulzt1#
O（n/log n）运行时间的一个来源是在一个机器模型中的位并行性，该机器模型具有对（log n）位字的恒定时间操作（单位成本随机存取机器）。一个n位位图需要O（n/log n）个字，因此并集、交集、差集等都需要O（n/log n）时间。