python - python bisect 是 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)

并绘制结果：

我会猜到/希望那insort会是 max O(nlog(n))。从文档中可以看出：

“请记住，O(log n) 搜索主要由缓慢的 O(n) 插入步骤支配。”

我在这里想念什么？

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

非常快的东西！

Answer 1

bisect是 O(logN)。但是，插入列表是 O(N)。你这样做N次。

从bisect.insort_left()文档中：

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

所以插入仍然是 O(N)，与此相比，O(logN) 搜索时间（渐近地说）微不足道。所以总的来说，你的定时测试需要 N 次 O(N) == O(N^2) 时间。