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) |
分享到:
相关推荐
数据结构与算法——C++版(第3版)源文件
Mark Allen Weiss《数据结构与算法——C++语言描述》原书第三版,中文
国外经典教材数据结构与算法——面向对象的C设计模式 国外经典教材数据结构与算法——面向对象的C设计模式
《数据结构与算法——C#语言描述,C# 数据结构 源代码 第一本C#数据结构的书
数据结构与算法——面向对象的C++设计模式
数据结构与算法——C++版(第2版)
数据结构与算法——看病排队候诊问题.docx
清晰完整的数据结构与算法——面向对象C++设计模式,需要的朋友可以下载
国外经典教材 数据结构与算法——面向对象的C++设计模式
数据结构与算法课设——医院候诊管理系统.docx数据结构与算法课设——医院候诊管理系统.docx数据结构与算法课设——医院候诊管理系统.docx数据结构与算法课设——医院候诊管理系统.docx数据结构与算法课设——医院...
数据结构与算法——C++版
数据结构与算法——简单的文本编辑器.pdf
数据结构与算法——C版的视频教学是浙江大学徐镜春老师讲解的。
数据结构与算法——线性表 定义线性表节点的结构.pdf
数据结构算法——Visual.C.6.0程序集].侯识忠.清晰。 节省硬盘资源,放在这里留用。
数据结构与算法——算法、时间空间复杂度、线性表 定义线性表节点的结构.pdf