2023年时间复杂度怎么算例题[时间复杂度的计算].docx

《2023年时间复杂度怎么算例题[时间复杂度的计算].docx》由会员分享，可在线阅读，更多相关《2023年时间复杂度怎么算例题[时间复杂度的计算].docx（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2023年时间复杂度怎么算例题时间复杂度的计算 时间困难度计算 学习数据结构时，觉得时间困难度计算很困难，怎么也看不懂，差不多三年之后，还是不懂，立刻就要找工作了，抓紧恶补一下吧： 首先了解一下几个概念。一个是时间困难度，一个是渐近时间困难度。前者是某个算法的时间耗费，它是该算法所求解问题规模n 的函数，而后者是指当问题规模趋向无穷大时，该算法时间困难度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间困难度，因此，在算法分析时，往往对两者不予区分，常常是将渐近时间困难度T(n)=O(f(n)简称为时间困难度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句

2、的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的状况下的时间困难度。以保证算法的运行时间不会比它更长。 常见的时间困难度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k 次方阶O(nk)、指数阶O(2n)。 1. 大O 表示法 定义 设一个程序的时间困难度用一个函数 T(n) 来表示，对于一个查找算法，如下： int seqsearch( int a, const int n, const int x) int i = 0; for (; ai != x &a

3、mp;& i if ( i = n) return -1; else return i; 这个程序是将输入的数值依次地与数组中地元素逐个比较，找出与之相等地元素。 在第一个元素就找到须要比较一次，在其次个元素找到须要比较2次， ，在第n 个元素找到须要比较n 次。对于有n 个元素的数组，假如每个元素被找到的概率相等，那么查找胜利的平均比较次数为: f(n) = 1/n (n + (n-1) + (n-2) + . + 1) = (n+1)/2 = O(n) 这就是传闻中的大O 函数的原始定义。 用大O 来表述 要全面分析一个算法，须要考虑算法在最坏和最好的状况下的时间代价，和在平均状况

4、下的时间代价。对于最坏状况，采纳大O 表示法的一般提法（留意，这里用的是“一般提法”）是：当且仅当存在正整数c 和n0, 使得 T(n) = n0 都成立。则称该算法的渐进时间困难度为T(n) = O(f(n)。这个应当是高等数学里面的第一章极限里面的学问。这里f(n) = (n+1)/2, 那么c * f(n)也就是一个一次函数。就是在图象上看就是假如这个函数在c*f(n)的下面，就是困难度为T(n) = O(f(n)。 对于对数级，我们用大O 记法记为O(log2N)就可以了。 规则 1） 加法规则 T(n,m) = T1(n) + T2(n) = O ( max (f(n), g(m)

5、) 2) 乘法规则 T(n,m) = T1(n) * T2(m) = O (f(n) * g(m) 3) 一个特例 在大O 表示法里面有一个特例，假如T1(n) O， c是一个与n 无关的随意常数，T2(n) = O ( f(n) ) 则有 T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) ). 也就是说，在大O 表示法中，任何非0正常数都属于同一数量级，记为O(1)。 4) 一个阅历规则 有如下困难度关系 c 其中c 是一个常量，假如一个算法的困难度为c 、 log2N 、n 、 n*log2N , 那么这个算法时间效率比较高 ，假如是 2n , 3

6、n ,n!, 那么略微大一些的n 就会令这个算法不能动了，居于中间的几个则差强人意. 1）基本学问点：没有循环的一段程序的困难度是常数，一层循环的困难度是O(n),两层循环的困难度是O(n2)? （我用2表示平方，同理 3表示立方）； 2）二维矩阵的标准差，残差，信息熵，fft2,dwt2,dct2的时间困难度: 标准差和残差可能O(n)，FFT2是O(nlog(n)，DWT2可能也是O(nlog(n)；信息熵要求概率，而dct 的过程和jpeg 一样。因为和jpeg 一样, 对二难矩阵处理了.Y=T*X*T，Z=Y.*Mask，这样子, 还有分成8*8子图像了; 3)example ： 1、

7、设三个函数f,g,h 分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请推断下列关系是否成立： （1） f(n)=O(g(n) （2） g(n)=O(f(n) （3） h(n)=O(n1.5) （4） h(n)=O(nlgn) 这里我们复习一下渐近时间困难度的表示法T(n)=O(f(n)，这里的O 是数学符号，它的严格定义是 若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n)表示存在正的常数C 和n0 ,使得当nn0时都满意 0T(n)C?f(n)。 用简单理解的话说就是这两个函数当整型自变

8、量n 趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。 (1)成立。题中由于两个函数的最高次项都是n3,因此当n时，两个函数的比值是一个常数，所以这个关系式是成立的。 （2）成立。与上同理。 （3）成立。与上同理。 （4）不成立。由于当n时n1.5比nlgn 递增的快，所以h(n)与nlgn 的比值不是常数，故不成立。 2、设n 为正整数，利用大O 记号，将下列程序段的执行时辰表示为n 的函数。 (1) i=1; k=0 while(i k=k+10*i;i+; 解答：T(n)=n-1， T(n)=O(n)， 这个函数是按线性阶递增的。 (2) x=n; / n>

9、1 while (x>=(y+1)*(y+1) y+; 解答：T(n)=n1/2 ，T(n)=O(n1/2)，最坏的状况是y=0，那么循环的次数是n1/2 次，这是一个按平方根阶递增的函数。 (3) x=91; y=100; while(y>0) if(x>100) x=x-10;y-; else x+; 解答： T(n)=O(1)，这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n 没有? 没。这段程序的运行是和n 无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分

10、析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间困难度和空间困难度来考虑。 1、时间困难度 （1）时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必需上机运行测试才能知道。但我们不行能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 （2）时间困难度 在刚才提到的时间频度中，n 称为问题的规模，当n 不断改变时，时间频度T(n)也会不断改变。但有时我们想知道它改变时呈现什

11、么规律。为此，我们引入时间困难度概念。 一般状况下，算法中基本操作重复执行的次数是问题规模n 的某个函数，用T(n)表示，若有某个协助函数f(n),使得当n 趋近于无穷大时，T （n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=(f(n),称(f(n) 为算法的渐进时间困难度，简称时间困难度。 在各种不同算法中，若算法中语句执行次数为一个常数，则时间困难度为O(1),另外，在时间频度不相同时，时间困难度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间困难度相同，都为O(n2)。 按数量级递增排列，常见的时间困难

12、度有： 常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),.， k 次方阶O(nk),指数阶O(2n)。随着问题规模n 的不断增大，上述时间困难度不断增大，算法的执行效率越低。 2、空间困难度 与时间困难度类似，空间困难度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n) 我们一般所探讨的是除正常占用内存开销外的协助存储单元规模。探讨方法与时间困难度类似，不再赘述。 （3）渐进时间困难度评价算法时间性能 主要用算法时间困难度的数量级(即算法的渐近时间困难度) 评价一个算法的时间性能。 【例37】有

13、两个算法A1和A2求解同一问题，时间困难度分别是 T1(n)=100n2，T2(n)=5n3。 （1）当输入量n 20时，有T1(n)T2(n)，后者花费的时间较少。 （2）随着问题规模n 的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时，算法A1比算法A2要有效地多。 它们的渐近时间困难度O(n2)和O(n3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间困难度和渐近时间困难度不予区分，而常常是将渐近时间困难度T(n)=O(f(n)简称为时间困难度，其中的f(n)一般是算法中频度最大的语句频度。 【例38】算法MatrixMu

14、ltiply 的时间困难度一般为T(n)=O(n3)，f(n)=n3是该算法中语句(5)的频度。下面再举例说明如何求算法的时间困难度。 【例39】交换i 和j 的内容。 Temp=i; i=j; j=temp; 以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n 无关的常数。算法的时间困难度为常数阶，记作T(n)=O(1)。 假如算法的执行时间不随着问题规模n 的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间困难度是O(1)。 【例310】变量计数之一。 (1) x=0;y=0; (2) for(k-1;k (3) x+; (4) for(

15、i=1;i (5) for(j=1;j (6) y+; 一般状况下，对步进循环语句只需考虑循环体中语句的执行次数，忽视该语句中步长加1、终值判别、限制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n2，所以该程序段的时间困难度为T(n)=O(n2)。 当有若干个循环语句时，算法的时间困难度是由嵌套层数最多的循环语句中最内层语句的频度f(n)确定的。 【例311】变量计数之二。 (1) x=1; (2) for(i=1;i (3) for(j=1;j (4) for(k=1;k (5) x+; 该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n 没有干脆

16、关系，但是却与外层循环的变量取值有关，而最外层循环的次数干脆与n 有关，因此可以从内层循环向外层分析语句(5)的执行次数： 则该程序段的时间困难度为T(n)=O(n3/6+低次项)=O(n3)。 （4）算法的时间困难度不仅仅依靠于问题的规模，还与输入实例的初始状态有关。 【例312】在数值A0.n-1中查找给定值K 的算法大致如下： (1)i=n-1; (2)while(i>=0&&(Ai!=k) (3) i-; (4)return i; 此算法中的语句(3)的频度不仅与问题规模n 有关，还与输入实例中A 的各元素取值及K 的取值有关: 若A 中没有与K 相等的元素，则语

17、句(3)的频度f(n)=n； 若A 的最终一个元素等于K, 则语句(3)的频度f(n)是常数0。 （5）最坏时间困难度和平均时间困难度 最坏状况下的时间困难度称最坏时间困难度。一般不特殊说明，探讨的时间困难度均是最坏状况下的时间困难度。 这样做的缘由是：最坏状况下的时间困难度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。 【例319】查找算法【例18】在最坏状况下的时间困难度为T(n)=0(n)，它表示对于任何输入实例, 该算法的运行时间不行能大于0(n)。 平均时间困难度是指全部可能的输入实例均以等概率出现的状况下，算法的期望运行时间。 常见的时间困难度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、k 次方阶0(nk)、指数阶0(2n)。明显，时间困难度为指数阶0(2n)的算法效率极低，当n 值稍大时就无法应用。 类似于时间困难度的探讨，一个算法的空间困难度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n 的函数。渐近空间困难度也经常简称为空间困难度。算法的时间困难度和空间困难度合称为算法的困难度。