一个算法中的语句执行次数称为语句频度或时间频度，记为T(n )。n 称为问题的规模，当n不断变化时，时间频度T(n )也会不断变化。但是有时候，我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数，是问题规模 n 的某个函数，用T(n )表示。若有某个辅助函数f(n ),使得当n 趋近于无穷大时，T(n )/f(n )的极限值为不等于零的常数，则称f(n )是T(n )的同数量级函数。记作T(n )=Ｏ(f(n )),称Ｏ(f(n )) 为算法的渐进时间复杂度。 时间频度不相同时，渐进时间复杂度Ｏ(f(n )) 有可能相同，如T(n )=n ^2+3n +4 与T(n )=4n ^2+2n +1 它们的频度不同，但时间复杂度相同，都为O(n ^2)。 ·现在我们根据一些书本上和网络上对时间复杂度概念的描述进行一下总结： T(n )，语句频度，时间频度，亦称为时间复杂度。 O(f(n ))，渐进时间复杂度。 前者 T(n )是某个算法的时间耗费，它是该算法所求解 问题规模 n 的函数，而后者 O(f(n ))是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度O(f(n ))，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n )=O(f(n ))简称为时间复杂度，其中的f(n )一般是算法中频度最大的语句频度。 注意：算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶 O(1)、对数阶 O(lo g2n )或O(lbn )、线性阶 O(n) 、线性对数阶 O(n *lo g2n )、 平方阶 O(n ^2)、立方阶 O(n ^3)、k 次方阶 O(n ^k)、指数阶 O(2^n )。 ·下面有一道题目是可以帮助同学们理解概念的： 1 、 设 三 个函数f,g,h分 别 为 f(n )=100*n ^3+n ^2+1000 , g(n )=25*n ^3+5000*n ^2 , h(n )=n ^1.5+5000*n *lgn 请判断下列关系是否成立： (1) f(n )=O(g(n )) (2) g(n )=O(f(n )) (3) h(n )=O(n ^1.5) (4) h(n )=O(n lgn ) 这里我们复习一下渐近时间复杂度的表示法T(n )=O(f(n ))，这里的"O"是数学符号，它的严格定义是 "若T(n )和 f(n )是定义在正整数集合上的两个函数，则T(n )=O(f(n ))表示存在正常数C和 n 0 ,使得当n ≥n 0 时...
VIP
