7

试图在python3中为我必须开发的 frotier 问题找到最优化的数据结构，我刚刚意识到使用模块bisect进行实时有序插入的复杂性不是 O(nlog n)，因为它应该是 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，所以它不是那么大。

任何帮助都感激不尽！

4

2 回答 2

14

您可能错过了时间复杂度为insortO (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（该sorted()函数使用的排序算法）只需要 O(m log m) 时间的解决方案。

于 2018-10-27T15:26:31.373 回答
4

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

原始代码片段中的_frontier命名暗示了某种优先搜索算法。堆可能更有意义，或者来自sortedcollections.

于 2018-10-27T15:22:13.220 回答