数据结构算法
Data Structure algorithm
如何在一般情况下按插入所需的时间复杂度的升序排列以下数据结构。
1.排序数组
2.哈希Table
3. 二叉搜索树
4. B+树
在这个回答中，我会给你一个关于每个数据结构的入门，剩下的让你自己完成。
- 排序数组：在大小为
k 的排序数组中，每个数组的问题
插入是你首先需要找到索引 i 所在的位置
应插入元素（简单），然后移动所有元素
i,i+1,...,k 向右以 "make place" 为新
元素。这需要 O(k) 时间，实际上平均移动 k/2 次。
因此，将元素插入排序数组的平均复杂度为 1/2 + 2/2 + 3/3 + ... + n/2 = (1+...+n)/2。
用sum of arithmetic progression看看它的复杂度是多少。
- 哈希 table 提供
O(1) 插入元素的平均分摊案例性能。当你做 n 操作时会发生什么，每个 O(1)？总复杂度是多少？
- 在二叉搜索树 (BST) 中，每个操作都是
O(h)，其中 h 是树的当前高度。幸运的是，当随机添加元素到二叉搜索树时（甚至非自平衡）its average height is still O(logn)。
因此，要获得添加所有元素的复杂性，您需要求和 Some_Const*(log(1) + log(2) + ...+ log(n))
见文末提示
- 与 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)
如何在一般情况下按插入所需的时间复杂度的升序排列以下数据结构。 1.排序数组 2.哈希Table 3. 二叉搜索树 4. B+树
在这个回答中，我会给你一个关于每个数据结构的入门，剩下的让你自己完成。
- 排序数组：在大小为
k的排序数组中，每个数组的问题 插入是你首先需要找到索引i所在的位置 应插入元素（简单），然后移动所有元素 i,i+1,...,k 向右以 "make place" 为新 元素。这需要O(k)时间，实际上平均移动k/2次。
因此，将元素插入排序数组的平均复杂度为1/2 + 2/2 + 3/3 + ... + n/2 = (1+...+n)/2。
用sum of arithmetic progression看看它的复杂度是多少。 - 哈希 table 提供
O(1)插入元素的平均分摊案例性能。当你做n操作时会发生什么，每个O(1)？总复杂度是多少？ - 在二叉搜索树 (BST) 中，每个操作都是
O(h)，其中h是树的当前高度。幸运的是，当随机添加元素到二叉搜索树时（甚至非自平衡）its average height is stillO(logn)。
因此，要获得添加所有元素的复杂性，您需要求和Some_Const*(log(1) + log(2) + ...+ log(n))
见文末提示 - 与 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)