algorithm - 数据结构算法

Question

如何按平均情况下插入所需的时间复杂度的升序排列以下数据结构。1.排序数组2.哈希表3. 二叉搜索树4. B+树

Answer 1

在这个回答中，我会给你一个关于每个数据结构的入门，让你自己完成剩下的。

1. 排序数组:在大小为 k 的排序数组中，每个数组的问题插入是你首先需要找到索引 i 所在的位置应插入元素(简单)，然后移动所有元素i,i+1,...,k 向右移动以便为新的“腾出位置”元素。这需要 O(k) 时间，实际上平均为 k/2 步。
   因此，将元素插入排序数组的平均复杂度是 1/2 + 2/2 + 3/3 + ... + n/2 = (1+...+n)/2。
   使用sum of arithmetic progression看看它的复杂性。
2. 哈希表提供 O(1) 插入元素的平均分摊情况性能。当你执行 n 操作时会发生什么，每个 O(1)？总的复杂性是多少？
3. 在二叉搜索树 (BST) 中，每个操作都是 O(h)，其中 h 是树的当前高度。幸运的是，当随机添加元素到二叉搜索树时(甚至非自平衡)its average height is still O(logn) .
   因此，要获得添加所有元素的复杂性，您需要求和 Some_Const*(log(1) + log(2) + ...+ log(n))
   见文末提示
4. 与 BST 类似，B+ 树每次插入也需要 O(h) 时间。不同之处在于，即使在最坏的情况下，h 也必然是对数的。因此，在计算平均情况时，时间复杂度的计算将保持 Some_Other_Const*(log(1) + log(2) + .. + log(n))。

提示:

• log(x) + log(y) = log(x*y)
• log(n!) 在O(nlogn)