简介
对于算法进行分析评估,通常是从时间与空间两种因数进行讨论的.
时间复杂度: 算法执行语句的次数.
空间复杂度: 算法在运行过程中临时占用储存大小的计算量度.
大O表示法(big-oh)
算法的时间复杂度通常用大O表示,一般用于界定函数集合的上界,可以称作渐进上界记号.
数学定义: 设T(n)和g(n)是定义域为自然数集N上的函数.若存在正常量c和n0,使得对一切n≥n0都有0≤T(n)≤cg(n)成立, 则称T(n)的渐进上界是g(n).表达式T[n]=O(g(n)),称为渐进时间复杂度.一般情况下,T[n]为算法基本操作重复执行的次数,g(n)是算法中频度最大的语句频率.
常见的时间复杂度(以算法平均情况归类):
| 序号 | 名称 | 例子 | 说明 |
|---|---|---|---|
| 1 | 常数阶O(1) | 哈希算法 | hash/普通的加减乘除等语句 |
| 2 | 对数阶O(logcn) | 二分查找 / 斐波那契数列 | 二分策略,底数c一般是2 |
| 3 | 线性阶O(n) | 线性查找 | 循环 |
| 4 | 线性对数阶O(nlogcn) | 归并排序 / 快速排序 / 希尔排序 / 堆排序 | 分治，底数c一般是2 |
| 5 | 平方阶O(n2) | 简单插入排序 / 简单选择排序 / 冒泡排序 | 双层循环,检查所有元素对 |
| 6 | 立方阶O(n3) | 全源最短路径 - floyd算法 | 三层循环,检查所有的三元组 |
| 7 | k次方阶O(nk) | DFS深度优先 | 发现从源节点可达的所有节点为止 |
| 8 | 指数阶O(2n) | 穷举查找 | 检查所有子集 |
| 9 | 阶乘O(n!) | 旅行商问题 |
其中O(logcn)、Ο(n)、O(nlogcn)、O(n2)、O(n3)和O(nk)称为多项式时间,而O(2n)和Ο(n!)称为指数时间.
计算机科学家普遍认为前者(即多项式时间复杂度的算法)是有效算法,把这类问题称为P(Polynomial,多项式)类问题,而把后者(即指数时间复杂度的算法)称为NP(Non-Deterministic Polynomial,非确定多项式)问题.
//求出1+2+3+4+……+100的和?
//示例1:
int sum = 0; //执行1次
int n=100; //执行1次
for (int i =1; i<=n; i++){ //执行n+1次
sum+=i; //执行n次
}
//g(n)=1+1+n+1+n=2n+3≈n(当n趋于∞时),故T(n)=O(n);
//示例2:
int sum =0; //执行一次
int n = 100; //执行一次
sum = (1+n)*n/2; //执行一次
//g(n)=3 与n无关的常数阶,故T(n)=O(1)
2
3
4
5
6
7
8
9
10
11
12
13
14
大Ω表示法(omega)
Ω也是一种时间复杂度的渐进表示法,一般用于界定函数集合的下界,可以称作渐进下界记号.
数学定义: 设T(n)和g(n)是定义域为自然数集N上的函数.若存在正常量c和n0,使得对一切n≥n0都有0≤cg(n)≤T(n)成立, 则称T(n)的渐进下界是g(n).表达式T[n]=Ω(g(n)).
大Θ表示法(theta)
Θ用于界定函数的渐进上界和渐进下界,可以称作渐进紧确界记号.
数学定义: 设T(n)和g(n)是定义域为自然数集N上的函数.若存在正常量c1、c2和n0,使得对一切n≥n0都有0≤c1g(n)≤cT(n)≤c2g(n)成立, 则称T(n)的渐进紧确界是g(n).表达式T[n]=Θ(g(n)).
小o表示法
由大O记号提供的渐进上界可能是渐进紧确的,也可能是非紧确的,用小o表示一个非渐进紧确的上界
数学定义: 设T(n)和g(n)是定义域为自然数集N上的函数.对任意正常量c>0,存在常量n0>0,使得对一切n≥n0都有0≤T(n)<cg(n)成立, 则称T(n)的非渐进紧确上界是g(n).表达式T[n]=o(g(n))
小w表示法
由大Ω记号提供的渐进下界可能是渐进紧确的,也可能是非紧确的,用小w表示一个非渐进紧确的下界
数学定义: 设T(n)和g(n)是定义域为自然数集N上的函数.对任意正常量c>0,存在常量n0>0,使得对一切n≥n0都有0≤cg(n)<T(n)成立, 则称T(n)的非渐进紧确下界是g(n).表达式T[n]=w(g(n))
← 散列