算法分析与时间复杂度
分类:
文章
•
2024-06-05 19:27:10
算法分析的数学基础
使用以下四个定义:
- 如果存在正常数c与n0,使得当N≥n0时,T(N) ≤ cf(N),则记为T(N) = O(f(N)). 也就是大O表示法
- 如果存在正常数c与n0,使得当N≥n0时,T(N) ≥ cf(N),则记为T(N) = Ω(f(N)) .也就是大Ω表示法
-
T(N) = Θ(h(N)) 当且仅当 T(N) = O(h(N)) ,且 T(N) = Ω(h(N)) .
- 如果 T(N) = O(p(N)) 且T(N) ≠ Θ(p(N)) , 则 T(N) = o(p(N)) .
总结:
通俗的说,这几种表示法可以理解如下:
-
大O表示法: f(x) = O(g(x)) 表示的含义是f(x)以g(x)为上界
-
小o表示法: f(x) = o(g(x)) 表示的含义是f(x)趋近于g(x)
-
Ω表示法:f(x) = Ω(g(x)) 表示的含义是f(x)以g(x)为下界
-
Θ表示法:f(x) = Θ(g(x)) 表示的含义是g(x)是f(x)的确界
算法的常见时间复杂度
![算法分析与时间复杂度 算法分析与时间复杂度](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzc5Mi8yMjM3NDZlNjdhNjI4MWQ5Mzc3ZDE5ZjdhZjM1YTcyOC5KUEVH)
由图中的时间复杂度增长趋势可以看出:
- 最优的算法复杂度为
logN
- 当 N 的值较小时,
NlogN < N
, 当 N 的值较大时,NlogN > N
- 指数次方与阶乘的复杂度非常高,一般不能使用这些算法,二次方或三次方的时间复杂度在N值较大是也是相当高的,在设计算法的时候必须要注意这一点