5.13.总结 - Python 数据结构

返回介绍

5.13.总结

发布于 2019-08-07 字数 496 浏览 787 评论 0

5.13.总结

  • 对于有序和无序列表,顺序搜索是 $$O(n)$$。
  • 在最坏的情况下,有序列表的二分查找是 $$O(logn)$$。
  • 哈希表可以提供恒定时间搜索。
  • 冒泡排序,选择排序和插入排序是 $$O(n^2)$$算法。
  • 希尔排序通过排序增量子列表来改进插入排序。它落在 $$O(n)$$ 和 $$O(n^2)$$ 之间。
  • 归并排序是 $$O(nlogn)$$,但是合并过程需要额外的空间。
  • 快速排序是 $$O(nlogn)$$,但如果分割点不在列表中间附近,可能会降级到$$O(n^2)$$ 。它不需要额外的空间。

上一篇:5.12.快速排序

下一篇:6.1.目标

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

目前还没有任何评论,快来抢沙发吧!