Bisect/Insort 的列表和双端队列的时间复杂度是否不同？

Question

据我所知，listPython中是使用数组实现的，而deque使用双链表实现的。无论哪种情况，某个值的二分查找都需要 O(logn) 时间，但如果我们插入到该位置，数组需要 O(n)，而双链表则需要 O(1)。

bisect那么，我们是否可以使用、 、insort和的组合deque来实现所有动态集合操作，并且时间复杂度可与 Java 中的 TreeMap 相媲美呢？

---

更新：我在这个Leetcode问题中测试了它：https ://leetcode.com/problems/time-based-key-value-store/submissions/

出乎我的意料，当我从 切换list到时deque，速度慢了很多。

Answer 1

对于你的标题问题：是的，他们这样做。

对于您假设的排序集实现问题：不，您不能。

一，你错误地执行了deque；它不是一个简单的“每个节点的项目”链表，而是每个节点的一个项目块（CPython 参考解释器上有 64 个项目，尽管这是一个实现细节）。除了头部和尾部块之外，内部块永远不会留空，因此中间插入deque并不是特别便宜，它仍然需要移动一堆东西。它不像O(n)中间list插入，因为它利用旋转的一些效率来旋转，附加到一侧或另一侧，然后旋转回去，但它与在链表中的已知点处插入相去甚远，剩余O(n)（尽管由于洗牌整个块比移动每个单独的项目更便宜，所以常数除数很大）。

第二， a 中的每次查找dequeis O(n)，而不是O(1)像 a list；如前所述，它的常数除数为 64，并且它下降到O(1)接近 的两端deque，但它仍然O(n)是一般情况，对于大 s 来说扩展性很差deque。bisect搜索是O(log n) 在假设序列索引为 的情况下进行的O(1)；对于 a deque，它们会是O(n log n)，因为它们会执行log n O(n)索引操作。这与您的测试结果相符；bisect+deque明显更差。

无论如何，JavaTreeMap并不是通过二分搜索和链表来实现的；链表对此没有好处，因为最终完整的二分搜索必须来回遍历足够多的内容才能完成O(n)全部工作，即使它只需要与O(log n)元素进行比较。树图需要某种树结构，你不能仅仅用链表和好的算法来伪造它。

内置替代方案包括：

1. insort正常的list：当然它是O(n)整体的，但是昂贵的部分（找到插入的位置）是O(log n)，并且它只是“腾出空间”步骤O(n)，而且它非常便宜O(n)（基本上是a memcpy）。对于真正巨大的 s 来说这是不可接受的list，但是您会惊讶地发现list您需要多大的 a 才能使开销相对于 Python 的缓慢而言变得明显。
2. 延迟、缓冲排序：如果查找不频繁，但插入很常见，则将排序推迟到需要时进行，以最大程度地减少排序操作的数量；只需将新元素附加到末尾而不进行排序并设置“需要排序”标志，并sort在设置标志时重新在查找之前。当输入已经大部分排序时，TimSort 算法表现得非常O(n)好（比没有对部分排序进行优化的通用排序通常更接近），因此它可能没问题。
3. 如果您在任何给定时间只需要最小元素，则heapq模块可以通过真正的插入和删除来实现O(log n)，并获取最小值O(1)（它始终为索引 0）。
4. 使用sqlite3数据库（可以通过shelve），适当索引；sqlite3索引默认使用 B 树，这意味着使用索引键排序的查询“免费”按排序顺序返回结果。

否则，您必须安装提供正确的类似排序类型的第三方模块set。