python bisect是O(n ^ 2)？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python bisect是O(n ^ 2)？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含889字，纯文字阅读大概需要2分钟。

内容图文

我正在运行一个简单的测试来监视使用bisect库排序插入列表需要多长时间

import numpy as np
import bisect

def get_time(N):
    myl = []
    a = time.time()
    for i in np.arange(N):
        bisect.insort_left(myl, random.randint(0,1000000) )
    b = time.time()
    return (b-a)

所以我称之为：

t_dict = {}
for N in [1000,5000,10000,50000,100000,200000,300000,400000,500000]:
    t_dict[N] = get_time(N)

并绘制结果：

我猜想/希望insort最大为O(nlog(n)).从文档中可以看出：

“请记住,O(log n)搜索主要是缓慢的O(n)插入步骤.”

我在这里错过了什么？

编辑：我错过了一些非常明显的东西.无论如何,我想使用SortedContainers包中的SortedList以同样的方式更新问题：

非常快的东西！

解决方法:

bisect是O(logN).但是,插入列表是O(N).你做了N次.

从bisect.insort_left() documentation：

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

因此插入仍为O(N),O(logN)搜索时间(渐近地)与此相比无关紧要.总的来说,你的定时测试花了N倍O(N)== O(N ^ 2)时间.

内容总结

以上是互联网集市为您收集整理的python bisect是O(n ^ 2)？全部内容，希望文章能够帮你解决python bisect是O(n ^ 2)？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端