您现在的位置: 精品资料网 >> 企业管理 >> 时间管理 >> 资料信息

时间复杂度分析教材(PPT 48页)

所属分类:
时间管理
文件大小:
344 KB
下载地址:
相关资料:
分析教材
时间复杂度分析教材(PPT 48页)内容简介
时间复杂度分析
算法时间复杂度的数学意义
从数学上定义,给定算法A,如果存在函数f(n),当n=k时,
f(k)表示算法A在输入规模为k的情况下的运行时间,则称f(n)为算法A的时间复杂度。
其中:输入规模是指算法A所接受输入的自然独立体的大小,
我们总是假设算法的输入规模是用大于零的整数表示的,即n=1,2,3,……,k,……
对于同一个算法,每次执行的时间不仅取决于输入规模,
还取决于输入的特性和具体的硬件环境在某次执行时的状态。所以想要得到一个统一精确的F(n)
是不可能的。为此,通常做法:1.忽略硬件及环境因素,假设每次执行时硬件条件和环境条件是完全一致的。
2.对于输入特性的差异,我们将从数学上进行精确分析并带入函数解析式。
算法的渐近时间复杂度很多时候,我们不需要进行如此精确的分析,究其原因:
1.在较复杂的算法中,进行精确分析是非常复杂的。
2.实际上,大多数时候我们并不关心F(n)的精确度量,而只是关心其量级。
算法复杂度的考察方法
(1)考察一个算法的复杂度,一般考察的是当问题复杂度n的增加时,运算所需时间、空间代价f(n)的上下界。
(2)进一步而言,又分为最好情况、平均情况、最坏情况三种情况。通常最坏情况往往是我们最关注的。
(1)上界函数
..............................
时间复杂度分析教材(PPT 48页)