数据结构与算法——算法速率
编程技术 / houtizong 发布于 3年前 65
O()表示法是处理近似计算的一种数学途径，当我们写下某个特定的排序算法对n个记录进行排序所需时间是O(n2)时，我们的意思是，最坏情况下，所需时间随着n的平方变化。O()表示法对我们在度量时间，内存等的值设置了上限。
有时我们会遇到复杂的O()函数，随着n的增大， 最高阶的项会主宰函数的值，习惯做法是去掉所有低阶项，对任何常数项不予考虑。如O(n2+3n)和O(n2)一样等价，这实际上是O()表示法的弱点。某个O(n2)算法可能比O(n2)算法快1000倍，但是从表示法中看不出来。
下面是一些常见的各种算法运行时间
附表一：
| O(1) | 常量访问（访问数组元素，简单语句） |
| O(lg(n)) | 对数型（二分查找）lg(n)是 log2n缩写 |
| O(n) | 线性型（顺序查找） |
| O(nlg(n)) | 比线性差，但不会差很多（快排，堆排序平均运行时间） |
| O(n2) | 平方律型（冒泡，选择，插入排序） |
| O(n3) | 立方型（2n × n矩阵相乘） |
| O(Cn) | 指数型（旅行家问题，集合划分） |
附表二：
| 排序法 | 最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
| 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 快速排序 | O(n2) | O(n*log2n) | 不稳定 | O(log2n)~O(n) |
| 选择排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 二叉树排序 | O(n2) | O(n*log2n) | 不一顶 | O(n) |
| 插入排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 堆排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
| 希尔排序 | O | O | 不稳定 | O(1) |
上一篇：数据结构与算法——二叉树遍历
请勿发布不友善或者负能量的内容。与人为善，比聪明更重要！
技术博客集 - 网站简介：
前后端技术：
后端基于Hyperf2.1框架开发,前端使用Bootstrap可视化布局系统生成
网站主要作用：
1.编程技术分享及讨论交流，内置聊天系统;
2.测试交流框架问题，比如：Hyperf、Laravel、TP、beego;
3.本站数据是基于大数据采集等爬虫技术为基础助力分享知识，如有侵权请发邮件到站长邮箱，站长会尽快处理;
4.站长邮箱：[email protected];
文章归档
文章标签
友情链接
