@@ -263,22 +263,22 @@ npm test -- 'playground'
263263| ** 队列** | n| n| 1| 1| |
264264| ** 链表** | n| n| 1| 1| |
265265| ** 哈希表** | -| n| n| n| 在完全哈希函数情况下，复杂度是 O(1）|
266- | ** 二分查找树** | n| n| n| n| 在平衡树情况下，复杂度是 O(logg (n))|
267- | ** B 树** | log(n)| log(n)| log(n)| log(n)| |
266+ | ** 二分查找树** | n| n| n| n| 在平衡树情况下，复杂度是 O(log (n))|
267+ | ** B 树** | log(n)| log(n)| log(n)| log(n)| |
268268| ** 红黑树** | log(n)| log(n)| log(n)| log(n)| |
269- | ** AVL 树** | log(n)| log(n)| log(n)| log(n)| |
269+ | ** AVL 树** | log(n)| log(n)| log(n)| log(n)| |
270270| ** 布隆过滤器** | -| 1| 1| -| 存在一定概率的判断错误（误判成存在）|
271271
272272###数组排序算法的复杂性
273273
274- | 名称| 最优| 平均| 最坏| 内存| 稳定| 备注|
274+ | 名称| 最优| 平均| 最坏| 内存| 稳定| 备注|
275275| ---------------------| :-------:| :-------:| :-----------:| :-------:| :-------:| ---------------------|
276- | ** 冒泡排序** | n| n^2| n^2| 1| Yes| |
277- | ** 插入排序** | n| n^2| n^2| 1| Yes| |
278- | ** 选择排序** | n^2| n^2| n^2| 1| No| |
279- | ** 堆排序** | n log(n)| n log(n)| n log(n)| 1| No| |
280- | ** 归并排序** | n log(n)| n log(n)| n log(n)| n| Yes| |
276+ | ** 冒泡排序** | n| n^2| n^2| 1| Yes| |
277+ | ** 插入排序** | n| n^2| n^2| 1| Yes| |
278+ | ** 选择排序** | n^2| n^2| n^2| 1| No| |
279+ | ** 堆排序** | n log(n)| n log(n)| n log(n)| 1| No| |
280+ | ** 归并排序** | n log(n)| n log(n)| n log(n)| n| Yes| |
281281| ** 快速排序** | n log(n)| n log(n)| n^2| log(n)| No| 在 in-place 版本下，内存复杂度通常是 O(log(n))|
282- | ** 希尔排序** | n log(n)| 取决于差距序列| n (log(n))^2| 1| No| |
283- | ** 计数排序** | n + r| n + r| n + r| n + r| Yes| r - 数组里最大的数|
284- | ** 基数排序** | n * k| n * k| n * k| n + k| Yes| k - 最长 key 的升序|
282+ | ** 希尔排序** | n log(n)| 取决于差距序列| n (log(n))^2| 1| No| |
283+ | ** 计数排序** | n + r| n + r| n + r| n + r| Yes| r - 数组里最大的数|
284+ | ** 基数排序** | n * k| n * k| n * k| n + k| Yes| k - 最长 key 的升序|