为什么平分比排序慢

Question

我知道 bisect 使用二分搜索来保持列表排序。但是我做了一个计时测试，这些值正在被读取和排序。但是，与我的知识相反，保留值然后对它们进行排序以高差赢得时机。请更有经验的用户解释这种行为吗？这是我用来测试时间的代码。

import timeit

setup = """
import random
import bisect
a = range(100000)
random.shuffle(a)
"""

p1 = """
b = []
for i in a:
    b.append(i)
b.sort()
"""

p2 = """
b = []
for i in a:
    bisect.insort(b, i)
"""

print timeit.timeit(p1, setup=setup, number = 1)
print timeit.timeit(p2, setup=setup, number = 1)

# 0.0593081859178
# 1.69218442959
# Huge difference ! 35x faster.

在第一个过程中，我逐个取值，而不是仅仅排序a以获得文件读取等行为。并且它非常努力地击败二等分。

Answer 1

对列表进行排序大约需要O(N*log(N))时间。将 N 项添加到列表需要O(N)时间。连续做这些事情需要O(N*log(N))时间。

将列表一分为二需要O(log(n))时间。将项目插入列表需要O(N)时间。在 for 循环中O(N * (N + log(n))) == O(N^2)同时执行 N 次需要时间。

O(N^2)比O(N*log(N))，所以你p1的比你的快p2。

Answer 2

在二等分的情况下，您的算法复杂性会更糟......

在这种bisect情况下，您有N操作（每个操作的平均成本是log(N)找到插入点，然后是O(N)插入项目的附加步骤）。 总复杂度： O(N^2) .

使用sort，您只需Nlog(N)一步（加上N O(1)首先构建列表的步骤）。 总复杂度：O(Nlog(N))

另请注意，它sort是在非常优化的 C 代码中实现的（bisect不是很优化，因为它最终会更频繁地调用各种比较函数......）