5.13. 总结
.. Copyright (C) Brad Miller, David Ranum This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/.
Summary¶
-
A sequential search is :math:
O(n)for ordered and unordered lists. -
A binary search of an ordered list is :math:
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 :math:
O(n^{2})algorithms. -
A Shell sort improves on the insertion sort by sorting incremental sublists. It falls between :math:
O(n)and :math:O(n^{2}). -
A merge sort is :math:
O(n \log{n}), but requires additional space for the merging process. -
A quicksort is :math:
O(n \log{n}), but may degrade to :math:O(n^{2})if the split points are not near the middle of the list. It does not require additional space.
创建日期: 2023年10月10日