5.13. 总结¶
5.13. Summary
- 顺序搜索对有序和无序列表的时间复杂度是 \(O(n)\)。
- 对有序列表进行二分搜索的最坏情况时间复杂度是 \(O(\log{n})\)。
- 哈希表可以提供常数时间的查找。
- 冒泡排序、选择排序和插入排序的时间复杂度都是 \(O(n^{2})\)。
- 希尔排序通过排序递增的子列表来改进插入排序。其时间复杂度介于 \(O(n)\) 和 \(O(n^{2})\) 之间。
- 归并排序的时间复杂度是 \(O(n \log{n})\)，但需要额外的空间来进行归并过程。
- 快速排序的时间复杂度是 \(O(n \log{n})\)，但如果划分点不在列表的中间附近，可能会退化为 \(O(n^{2})\)。它不需要额外的空间。
- A sequential search is \(O(n)\) for ordered and unordered lists.
- A binary search of an ordered list is \(O(\log{n})\) in the worst case.
- Hash tables can provide constant time searching.
- A bubble sort, a selection sort, and an insertion sort are \(O(n^{2})\) algorithms.
- A Shell sort improves on the insertion sort by sorting incremental sublists. It falls between \(O(n)\) and \(O(n^{2})\).
- A merge sort is \(O(n \log{n})\), but requires additional space for the merging process.
- A quicksort is \(O(n \log{n})\), but may degrade to \(O(n^{2})\) if the split points are not near the middle of the list. It does not require additional space.
最后更新:
2024年9月13日
创建日期: 2024年9月9日
创建日期: 2024年9月9日