SortedList 中操作的时间复杂度 - Python

Question

SortedContainers 模块的 SortedList 实现中操作的时间复杂度是多少？据我了解，底层数据结构是数组列表。那么插入是否需要O(n)时间，因为可以找到索引O(logn)然后将元素插入到正确的位置是O(n)？类似地，从索引中弹出元素也必须O(n)如此。

Answer 1

插入、删除、获取索引、左右平分、在列表中查找元素都是 log(n) 操作。它类似于java和c++中的treeset和multiset，用AVL树或红黑树实现。