|
对时间复杂度进行估计的时候，从区域规模为充分大的时候，做一个估计量就可以了，所以在这里引入三种表示方法：上界、下限，等同阶的?表示法。
渐进性态的阶
设f(n)和 g (n) 是定义在正整数集上的正函数
Notes:这里的“=”并不是数学上的那个等于，而是一种表示方法
(1)大O表示法 (算法运行时间的上限 )
若?正常数c和 自然数N0 使得当 n ? N0 时,有f(n)? cg (n) 则称函数 f(n )在n充分大时有上界, 且 g(n)是它一个上界.记为 f(n) =O(g (n)) , 也称 f(n) 的阶不高于g (n) 的阶.
例如，3n=O(n), n+1024=O(n), 2n2+11n-10=O(n2)
(2) 大Ω表示法 (算法运行时间的下限）
若Ω正常数c和自然数N0使得当 n ? N0 时,有f(n)?c g(n) 则称函数f(n)在n充分大时有下限, 且 g(n)是它的一个下限,记为f(n) = ? (g (n) ) 也称f (n)的阶不低于 g(n)的阶。
(3) θ表示法
f (n) =?(g(n) )等价于 f(n)=O(g (n) ) 且 f(n)=?(g (n) )
称函数f(n)与g(n) 同阶.
例 T(n)=c1n2+c2n , 则 T(n)= ? (n2),
时间复杂度是根据输入规模而言的，时间增长的快慢有很多的不同，可以看到当时间复杂度为指数型的时候，n=40这个不太大的规模已经需要计算半个月之久。
| T(n)微秒 | logn | n | nlogn | n2 | n3 | n5 | 2n | 3n | n! |
|---|
| n=10 | 3.3 | 10 | 33 | 100 | 1毫秒 | 0.1秒 | 1毫秒 | 59毫秒 | 3.6秒 | | n=40 | 5.3 | 40 | 213 | 1600 | 64毫秒 | 1.7分 | 12.7天 | 3855世纪 | 103世纪 | | n=60 | 5.9 | 60 | 354 | 3600 | 216毫秒 | 1.3分 | 366世纪 | 1.3×1013世纪 | 1066世纪 |
硬件性能提升可以改变计算的速度，但是仍然不能弥补算法的缺陷，所以需要有效算法。
不同T(n)的算法当n增长时运算时间增长的快慢很不同。T(n)为指数形式的算法当n较大时实际上是无法应用的。有些算法T(n)与n！成正比，它随n的加大比指数函数增长还要快，这种算法更是没有实用价值。凡是T(n)为n的对数函数、线性函数或多项式的(幂函数也是多项式的特例)，称为“有效算法”。
|