python 平分是 O(n^2)？

Question

我是运行一个简单的测试，用于监控使用 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)

并绘制结果：

我会 guessed/hoped insort 最大 O(nlog(n))。从文档中可以看出：

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

我在这里错过了什么？

编辑：我遗漏了一些非常明显的东西。无论如何，我想使用 SortedContainers 包中的 SortedList 用同样的东西更新问题：

非常快的东西！

Answer 1

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 平分是 O(n^2)？

python bisect is O(n^2)?

python

algorithm

big-o

bisection