《数据结构时间复杂度讲解.docx》由会员分享，可在线阅读，更多相关《数据结构时间复杂度讲解.docx（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。n称为问题的规模，当n 不断变化时，时间频度T(n)也会不断变化。但是有时候，我们想知道它变化时呈现什么规律。 为此，我们引入时间简单度概念。一般状况下，算法中基本操作重复执行的次数，是问题规模n的某个函数，用T(n) 表示。若有某个帮助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常 数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n),称O(f(n)为算法的渐进时间简单 度。时间频度不相同时，渐进时间简单度。(f(n)有可能相同，如T(n尸n八2+3n+4与 T(n)=4n八2+2n
2、+l它们的频度不同，但时间简单度相同，都为0(22)。现在我们依据一些书本上和网络上对时间简单度概念的描述进行一下总结：T(n),语句频度，时间频度，亦称为时间简单度。0(f(n),渐进时间简单度。前者T(n)是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者0(f(n) 是指当问题规模趋向无穷大时，该算法时间简单度的数量级。当我们评价一个算法的时间性 能时，主要标准就是算法的渐近时间简单度0(f(n),因此，在算法分析时，往往对两者不 予区分，常常是将渐近时间简单度T(n)=0(f(n)简称为时间简单度，其中的f(n)一般是算法 中频度最大的语句频度。留意：算法中语句的频度不仅与
3、问题规模有关，还与输入实例中各元素的取值相关。但是我 们总是考虑在最坏的状况下的时间简单度。以保证算法的运行时间不会比它更长。常见的时间简单度，按数量级递增排列依次为：常数阶0(1)、对数阶O(log2n)或0(lbn)、线 性阶0(n)、线性对数阶O(n*log2n)、平方阶0(n八2)、立方阶0(n八3)、k次方阶0(Mk)、指数阶0(2八n)。下面有一道题目是可以关心同学们理解概念的：1、设三个函数 f,g,h 分别为 f(n100*nA3+nA2+1000 , g(n)=25*M3+5000*n八2 , h(n)=nA 1.5+5000*n*lgn请推断下列关系是否成立：(1) f(n
4、)=O(g(n)g(n)=O(f(n) h(n0(nA1.5)h(n)=O(nlgn)这里我们复习一下渐近时间简单度的表示法T(n)=O(f(n),这里的是数学符号，它的严格 定义是若T(n)和f(n)是定义在正整数集合上的两个函数,则T(n)=O(f(n)表示存在正常数C 和nO,使得当nnO时都满意OWT(n)WC*f(n)。”(即书本中的定义)。通俗一点就是这两个 函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。 (1)成立。题中由于两个函数的最高次项都是n八3,因此当n-8时，两个函数的比值是一 个常数，所以这个关系式是成立的。 (2)成立。与上同理。 (3)成立。与
5、上同理。 (4)不成立。由于当n-8时.1.5比n*lgn递增的快，所以h(n)与nlgn的比值不是常数, 故不成立。理解完概念之后，就开头求算法的时间简单度。从概念中我们知道，要求时间简单度O(f(n),就必需要知道算法中频度最大的语句频度f(n), 那么要求最大的语句频度f(n)就必需要知道算法的语句频度T(n)o一般总的思路就是：T(n)-f(n)-0(f(n)o有时候可以直接找到算法中频度最大的语句，直接算出f(n),然后写出O(f(n)。也有例外状况就是很难求出语句频度T(n)的下面会用一些例子做具体的说明：0(1)例 1 ： Temp=i;i=j;j=temp;以上三条单个语句的频
6、度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算 法的时间简单度为常数阶，记作T(n)=0(l)。假如算法的执行时间不随着问题规模n的增加 而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间 简单度是0(1)。例 2： x=91; y=100;while(y0)if(x100)x=x-10;y-;else x+;解答：T(n0(l),这个程序看起来有点吓人，总共循环运行了 1000次，但是我们看到n 没有？没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个 常数阶的函数。O(n)例1：i=l; k=0while(in) k=k+
7、10*i;i+;)解答：T(n)=n-1, T(n)=O(n),这个函数是按线性阶递增的。例2：a=0;b=l;for (i=l;i=n;i+)s=a+b;b=a;a=s;)解：语句1的频度：2,语句2的频度：n,语句3的频度：n-1,语句4的频度：n-1, 语句5的频度：n-1,T(n)=2+n+3(n-1 )=4n-1 =0(n).0(nA2)例1：交换i和j的内容sum=0；(一次)for(i=l;i=n;i+)(n 次 )for(j=l;j=n;j+) (n八2 次)sum+；(n八2次)(此语句是算法中频度最大的，可直接算出f(n)=n八2,得时间简单度T(n)=0(nA2)解：T(
8、n)=2nA2+n+l =0(nA2)例2：for (i=l;in;i+)(y=y+1;for (j=0;j=(2*n);j+) x+;)解：语句1的频度是n-1语句 2 的频度是(n-1 )*(2n+l)=222-n-lf(n)=2nA2-n-1 +(n-1 )=2nA2-2 该程序的时间简单度T(n)=0(nA2).0(nA3)例1：for(i=0;in;i+)for(j=0;ji;j+)(此语句为频度最大的语句，可算出f(n尸n八3,写出时间for(k=0;kj;k+) x=x+2;简单度 T(n)=0(nA3)解：当i=m, j=k的时候，内层循环的次数为k当i=m时,j可以取,所以这里最内 循环共进行了 0+l+.+m-l=(m-l)m/2次所以,i从。取到n,则循环共进行了： 0+( 1 -1 )* 1 /2+.+(n-1 )n/2=n(n+1 )(n-1 )/6 所以时间简单度为 O(nA3).O(log2n)(此为例外状况，难以算出T(n),但可以采用技巧直接算出O(f(n)。) 例1：i=l； while (i=n)i=i*2;解：语句1的频度是1,设语句 2 的频度是 f(n),则：2Af(n)=n;f(n)=log2n取最大值f(n)= log2n,T(n)=O(log2n )0(1)