文档介绍：时间复杂度分析
算法时间复杂度的数学意义
从数学上定义,给定算法A,如果
存在函数f(n),当n=k时,f(k)表示算法
A在输入规模为k的情况下的运行时间,
则称f(m)为算法A的时间复杂度。
其中:输入规模是指算法A所接受输入的自然独立体
的大小,我们总是假设算法的输入规模是用大于零
的整数表示的,即n=1,2,3
对于同一个算法,每次执行的时间不仅
取决于输入规模,还取决于输入的特性和具
体的硬件环境在某次执行时的状态。所以想
要得到一个统一精确的F(n)是不可能的。为
此,通常做法
忽略硬件及环境因素,假设每次执行时
硬件条件和环境条件是完全一致的
,我们将从数学上
进行精确分析并带入函数解析式。
例子:
for(i=1;<=n;i++)
forgj=l;j<=i;j++
for(k=l; k<=j; k++)
x+十
x++运行次数:
D
算法的渐近时间复杂度
很多时候,我们不需要进行如此精
确的分析,究其原因
在较复杂的算法中,进行精确分
析是非常复杂的。
,大多数时候我们并不关
心F(n)的精确度量,而只是关心其量级
算法复杂度的考察方法
(1)考察一个算法的复杂度,一般考察
的是当问题复杂度n的增加时,运算所
需时间、空间代价f(n)的上下界。
(2)进一步而言,又分为最好情况、平
均情况、最坏情况三种情况。通常最
坏情况往往是我们最关注的。
(1)上界函数
定义1如果存在两个正常数c和n,对于所有的n≥n0有
T(n)≤cf(n)
则记作T(n)=O(f(n))
含义:
如果算法用n值不变的同一类数据在某台机器上运很
所用的时间总是小于f(m)的一个常数倍。所以f(是
计算时间T(n)的一个上界函数
试图求出最小的f(n),使得T(n)=O(f(n))。
f(n)
T(n)
n
T(n)=o(f(n)
在分析算法的时间复杂度时,我们更关心最坏
情况而不是最好情况,理由如下:
(1)最坏情况给出了算法执行时间的上界,我
们可以确信,无论给什么输入,算法的执
行时间都不会超过这个上界,这样为比较
和分析提供了便利。
(2)虽然最坏情况是一种悲观估计,但是对于
很多问题,平均情况和最坏情况的时间复
杂度差不多,比如插入排序这个例子,平
均情况和最坏情况的时间复杂度都是输入
长度n的二次函数
(2)下界函数
定义12如果存在两个正常数c和n,对于所有的n≥n
有
T(n)≥c|g(n)
则记作T(n)=9(g(m)
含义
如果算法用n值不变的同一类数据在某台机器上运时
所用的时间总是不小于g(m)的一个常数倍。所以』)
是计算时间T(n)的一个下界函数。
试图求出“最大”的g(n),使得T(n)=9(g(n))