bisect.insort复杂度不像预期的那样

Question

为了在python3中为一个更复杂的问题寻找最优的数据结构，我刚刚意识到使用模块bisect进行实时有序插入的复杂性不是O(nlog n)，而是成倍增长的。我不知道这是怎么回事，所以想问问你们，以防万一，因为我觉得这很有趣。

想一想，我正确地使用了这个模块，所以这对我来说不应该是一个问题，无论如何，这里是用来插入节点对象的代码，它决定了由一个随机的f值节点所做的插入。

bisect.insort(self._frontier, (node._f, node))

在几秒钟内得到很多物体，但随着时间的推移，却没有那么多。巴库建议我问这个问题，因为他在做了一些测试后发现这个问题很有趣，结果和我一样。他用来测试这个结果的代码如下：

python3 -m timeit -s 'import bisect as B; import random as R;seq=[]' 'for _ in range(100000):B.insort(seq, R.randint(0, 1000000))'

A这些是他的结论：

10k的插入都很好(80 is之前，它基本上是线性缩放的，请记住它是O(nlog n)，所以它比线性稍微差一点)，但是在100 k时，它要花费很长时间，而不是10倍。100 k元素的列表并不是很大，log(100 K)是16，所以没有那么大。

任何帮助都将不胜感激！

Answer 1

您可能忽略了insort的时间复杂度是O(n)，这是bisect.insort_left()

请记住，O(log )搜索是由缓慢的O(n)插入步骤主导的。

找到插入点很便宜，但是插入到Python列表中并不便宜，因为通过插入点的元素必须向前移动一步。

还请参阅Python上的TimeComplexity页面，其中记录了list插入：

插入O(n)

您可以在O(log )时间内找到插入点，但后面的插入步骤是O( n)，这是一种相当昂贵的排序方法。

如果使用此方法对m个元素进行排序，则有一个O(m^2) (二次)解，用于TimSort ( sorted()函数使用的排序算法)只需O( m )时间的问题。

Answer 2

二进制搜索需要O(log )比较，但insort不仅仅是二进制搜索。它还插入元素，并将元素插入长度-n列表需要O(n)时间。

原始代码片段中的_frontier命名提出了某种排序搜索算法。堆可能对此更有意义，或者是来自sortedcollections的一个sortedcollections。