我读到Python 的列表是使用指针实现的。然后我看到这个模块 http://docs.python.org/2/library/bisect.html它可以有效地插入到排序列表中。它是如何有效地做到这一点的?如果列表是使用指针而不是通过连续数组实现的,那么如何有效地搜索插入点呢?如果列表是通过连续数组支持的,那么在插入元素时必须进行元素移位。那么这个bisect
如何有效地工作呢?
最佳答案
我相信列表的元素是指向的,但“列表”实际上是一个连续的数组(在 C 中)。它们被称为列表,但它们不是链接列表。
实际上,在排序列表中查找元素非常好 - 时间复杂度为 O(logn)。但插入并不是那么好 - 它是 O(n)。
如果你需要一个logn数据结构,最好使用treap树或红黑树。
关于python - Python 的二分法如何工作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20255294/