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

概述我在 python中寻找一个数据结构(在这个例子中由％分隔),它可以有效地(O(ln n)或更好…)按顺序执行插入： insert ( 6, % 3, 4, 9 %) -> % 3, 4, 6, 9 % 对于list和np.ndarray,它是O(n).字典或集合是无序的. 有内置(或没有)方法吗？ 清单？ bisect可以帮助你,至少在寻找应该插入元素的位置时(O(log n))： impor 我在 python中寻找一个数据结构(在这个例子中由％分隔),它可以有效地(O(ln n)或更好…)按顺序执行插入：

insert ( 6,% 3,4,9 %) ->  % 3,6,9 %

对于List和np.ndarray,它是O(n).字典或集合是无序的.

有内置(或没有)方法吗？

解决方法 清单？

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

import bisectl = [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

总结

以上是内存溢出为你收集整理的python – 在O(ln n)中按有序序列插入值全部内容，希望文章能够帮你解决python – 在O(ln n)中按有序序列插入值所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。