我正在为某种内存管理实现 2-3-4 树。在我的应用程序初始化期间，我想在那里插入一些整数（将其作为输入 - 比如说 n）这种插入的复杂性是什么？O（nloglog（n））？
问问题
1115 次
1 回答
2
在 2-3-4 树上插入的复杂度是 O(log(n))。
我们可以从维基百科看到一个配额
2-3-4 树是 4 阶 B-树 (Knuth 1998)
在 B-tree 上插入的复杂度是 O(log(n))，2-3-4 树也是如此。通过重复插入来初始化 2-3-4 树，我们可以说 init 的时间成本是 O(n*log(n))。但是我们可以期待一种特殊的方式来构造 [ link ]：
在应用程序中，构建 B-tree 来表示现有的大量数据集合，然后使用标准 B-tree 操作增量更新它通常很有用。在这种情况下，构造初始 B 树最有效的方法不是将初始集合中的每个元素依次插入，而是直接从输入构造初始叶节点集，然后从这些叶节点构建内部节点。这种构建 B 树的方法称为批量加载。最初，除了最后一个之外，每个叶子都有一个额外的元素，将用于构建内部节点。
时间成本可能是 (n + n/4 + n/16 + ... + n/(4^h))。基于几何级数的总和。我计算时间成本。它小于 (4/3)*n。
如果我在计算过程中有任何错误，请指出。
于 2013-11-29T03:08:55.960 回答