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日