python – 在O(ln n)中按有序序列插入值

bisect可以帮助你,至少在寻找应该插入元素的位置时(O(log n))：

import bisect
l = [3,9]
bisect.insort_left(l,6)
print(l)
# [3,9]

但是从文档中可以看出：

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

所以列表确实是一个问题,而不是搜索本身. Python TimeComplexity’s table没有显示O(log n)插入的任何替代方法.

二叉搜索树

从这个table开始,看起来“二进制搜索树”具有访问,搜索和插入的O(log n).还有其他结构也符合要求,但这可能是最知名的.

这answer (Implementing binary search tree)应该可以帮到你.举个例子 ：

r = Node(3)
binary_insert(r,Node(9))
binary_insert(r,Node(4))
binary_insert(r,Node(6))

in_order_print(r)
# 3
# 4
# 6
# 9