数据结构与算法——算法速率
程序员文章站
2022-07-12 17:26:44
...
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) |
上一篇: 数据结构(java版)
推荐阅读