數據結構算法

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)？什麼將是共同的coplexity？
3. 在二叉搜索樹（BST）中，每個操作是O(h)，其中h是樹的當前高度。幸運的是，當將元素隨機添加到二叉搜索樹（甚至非自平衡）its average height is still O(logn)時。
   所以，要想讓加入所有元素的複雜性，需要在年底
4. 總結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)