bisect.insort复杂性与预期不符

Question

试图在python3中找到最优化的数据结构以解决一个更严重的问题，我不得不开发，这才刚刚意识到，使用模块二等分进行实时有序插入的复杂性不是O（nlog n），而是应该成倍增长。代替。不知道它的原因，所以感觉就像问你们，以防万一，因为我发现它真的很有趣。

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

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

在几秒钟之内得到很多物体，但是随着时间的流逝就没有那么多。Bakuriu建议我问这个问题，因为他在进行了一些测试并得出与我相同的结果后也发现它很有趣。他用来测试的代码如下：

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

这些是他的结论：

10k插入都很好（到80ms为止，它基本上是线性扩展的（请记住，它是O（nlog n），所以比线性还差一点）），但是100k插入将永远花费而不是10倍以上。100k元素的列表实际上并不大，log（100k）为16，所以它并不大。

任何帮助都感激不尽！

Answer 1

你可能错过了的时间复杂度insort为O（N） ，这是明确记载为bisect.insort_left()：

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

查找插入点很便宜，但是插入到Python列表中并不是很方便，因为插入点之后的元素必须向上移动。

另请参见Python Wiki上的TimeComplexity页面，其中记录了list插入操作：

插入O（n）

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

如果使用此方法对m个元素进行排序，则可以使用O（m ^ 2）（二次）解决方案，该解决方案使用TimSort（该函数使用的排序算法）只需花费O（m log m）时间sorted()。