时间复杂度 以你之姓@ 2024-04-18 11:04 94阅读 0赞 # **时间复杂度** # ## **一、时间复杂度的定义** ## 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,**T(n)/f(n)**的极限值为不等于零的常数,则称f(n)是T(n)的**同数量级函数**。记作**T(n)=O(f(n))**,称**O(f(n))**为算法的**渐进时间复杂度**(*O**是数量级的符号* ),简称**时间复杂度**。 定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 ,则T(n)称为这一算法的“**时间复杂性**”。 当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“**渐近时间复杂性**”。 我们常用大O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是最大上界,但人们在表示的时候一般都习惯表示前者。 此外,一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。 “大O记法”:在这种描述中使用的基本参数是 n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order),比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时,运行时间至多将以正比于 f(n)的速度增长。 这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差异。例如,一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。 # # ## **二、时间复杂度计算步骤**** ** ## ### 1. 计算出基本操作的执行次数T(n) ### 基本操作即算法中的每条语句(以;号作为分割),语句的执行次数也叫做语句的频度。在做算法分析时,一般默认为考虑最坏的情况。 ### 2. 计算出T(n)的数量级 ### 求T(n)的数量级,只要将T(n)进行如下一些操作: 忽略常量、低次幂和最高次幂的系数。 令f(n)=T(n)的数量级。 ### 3. 用大O来表示时间复杂度 ### int num1, num2; for(int i=0; i<n; i++) { num1 += 1; for(int j=1; j<=n; j*=2) { num2 += num1; } } 当n趋近于无穷大时,如果lim(T(n)/f(n))的值为不等于0的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。 ## **三、时间复杂度计算举例** ## ### **正常计算的计算步骤** ### 分析: ① > 语句int num1, num2;的频度为1; > > 语句i=0;的频度为1; > > 语句i<n; i++; num1+=1; j=1; 的频度为n; > > 语句j<=n; j\*=2; num2+=num1;的频度为n\*log2n; > > T(n) = 2 + 4n + 3n\*log2n ② 忽略掉T(n)中的常量、低次幂和最高次幂的系数。 f(n) = n\*log2n ③ lim(T(n)/f(n)) = (2+4n+3n\*log2n) / (n\*log2n) = 2\*(1/n)\*(1/log2n) + 4\*(1/log2n) + 3 当n趋向于无穷大,1/n趋向于0,1/log2n趋向于0 所以极限等于3。 T(n) = O(n\*log2n) **简化的计算步骤** 再来分析一下,可以看出,决定算法复杂度的是执行次数最多的语句,这里是num2 += num1,一般也是最内循环的语句。 并且,通常将求解极限是否为常量也省略掉? 于是,**以上步骤可以简化为:** 1. 找到执行次数最多的语句 2. 计算语句执行次数的数量级 3. 用大O来表示结果 继续以上述算法为例,进行分析: ① 执行次数最多的语句为num2 += num1 ② T(n) = n\*log2n f(n) = n\*log2n ③ // lim(T(n)/f(n)) = 1 T(n) = O(n\*log2n) \------------------------------------------------------------------------------- **一些补充说明** 最坏时间复杂度 算法的时间复杂度不仅与语句频度有关,还与问题规模及输入实例中各元素的取值有关。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的运行时间不会比任何更长。 求数量级 即求对数值(log),默认底数为10,简单来说就是“一个数用标准科学计数法表示后,10的指数”。例如,5000=5x10 3 (log5000=3) ,数量级为3。另外,一个未知数的数量级为其最接近的数量级,即最大可能的数量级。 求极限的技巧 要利用好1/n。当n趋于无穷大时,1/n趋向于0 \------------------------------------------------------------------------ **一些规则(引自:[时间复杂度计算][Link 1]** **)** 1) 加法规则 T(n,m) = T1(n) + T2(n) = O (max ( f(n), g(m) ) 2) 乘法规则 T(n,m) = T1(n) \* T2(m) = O (f(n) \* g(m)) 3) 一个特例(问题规模为常量的时间复杂度) 在大O表示法里面有一个特例,如果T1(n) = O(c), 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 < log2n < n < n\*log2n < n^2 < n^3 < 2^n < 3^n < n! (c是一个常量) |------------------|-------------------|-------------| 较好 一般 较差 其中c是一个常量,如果一个算法的复杂度为c 、 log2n 、n 、 n\*log2n,那么这个算法时间效率比较高 ,如果是 2n , 3n ,n!,那么稍微大一些的n就会令这个算法不能动了,居于中间的几个则差强人意。 理解补充 1.一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 2.一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))。随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。 在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n),求极限可得到一常数c,则时间复杂度T(n)=O(f(n))。 3.常见的时间复杂度 按数量级递增排列,常见的时间复杂度有: 常数阶O(1), 对数阶O(log2n), 线性阶O(n), 线性对数阶O(nlog2n), 平方阶O(n^2), 立方阶O(n^3),..., k次方阶O(n^k), 指数阶O(2^n) 。 其中, 1. O(n),O(n^2), 立方阶O(n^3),..., k次方阶O(n^k) 为多项式阶时间复杂度,分别称为一阶时间复杂度,二阶时间复杂度。。。。 2.O(2^n),指数阶时间复杂度,该种不实用。 3.对数阶O(log2n), 线性对数阶O(nlog2n),除了常数阶以外,该种效率最高。 例:算法: for(i=1;i<=n;++i) { for(j=1;j<=n;++j) { c[ i ][ j ]=0; //该步骤属于基本操作 执行次数:n^2 for(k=1;k<=n;++k) c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作执行次数:n^3 } } 则有 T(n)= n^2+n^3,根据上面括号里的同数量级,我们可以确定 n^3为T(n)的同数量级; 则有f(n)= n^3,然后根据T(n)/f(n)求极限可得到常数c; 则该算法的 时间复杂度:T(n)=O(n^3)。 ## **四、时间复杂度各种情况分析** ## ### 1.并列循环的复杂度分析 ### 将各个嵌套循环的时间复杂度相加。 例如: for (i=1; i<=n; i++) x++; for (i=1; i<=n; i++) for (j=1; j<=n; j++) x++; 解: 第一个for循环 T(n) = n f(n) = n 时间复杂度为Ο(n) 第二个for循环 T(n) = n^2 f(n) = n^2 时间复杂度为Ο(n2) 整个算法的时间复杂度为Ο(n+n2) = Ο(n2)。 ### 2.函数调用的复杂度分析 ### 例如: public void printsum(int count)\{ int sum = 1; for(int i= 0; i<n; i++)\{ sum += i; \} System.out.print(sum); \} 分析: 记住,只有可运行的语句才会增加时间复杂度,因此,上面方法里的内容除了循环之外,其余的可运行语句的复杂度都是O(1)。 所以printsum的时间复杂度 = for的O(n)+O(1) = 忽略常量 = O(n)。 这里其实可以运用公式 num = n\*(n+1)/2,对算法进行优化,改为: public void printsum(int count)\{ int sum = 1; sum = count \* (count+1)/2; System.out.print(sum); \} 这样算法的时间复杂度将由原来的O(n)降为O(1),大大地提高了算法的性能。 ### 3.混合情况(多个方法调用与循环)的复杂度分析 ### 例如: public void suixiangMethod(int n)\{ printsum(n);//1.1 for(int i= 0; i<n; i++)\{ printsum(n); //1.2 \} for(int i= 0; i<n; i++)\{ for(int k=0; k System.out.print(i,k); //1.3 \} \} suixiangMethod 方法的时间复杂度需要计算方法体的各个成员的复杂度。 也就是1.1+1.2+1.3 = O(1)+O(n)+O(n2) ----> 忽略常数 和 非主要项 == O(n2) \----------------------------------------------------------------------- ### **更多的例子** ### **O(1)**** ** 交换i和j的内容 temp=i; i=j; j=temp; 以上三条单个语句的频度为1,该程序段的执行时间是一个与问题规模n无关 的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 **O(n^2)**** ** sum=0; /\* 执行次数1 \*/ for(i=1;i<=n;i++) for(j=1;j<=n;j++) sum++; /\* 执行次数n2 \*/ 解:T(n) = 1 + n2 = O(n2) for (i=1;i<n;i++) \{ y=y+1; ① for (j=0;j<=(2\*n);j++) x++; ② \} 解:语句1的频度是n-1 语句2的频度是(n-1)\*(2n+1) = 2n2-n-1 T(n) = 2n2-n-1+(n-1) = 2n2-2 f(n) = n2 lim(T(n)/f(n)) = 2 + 2\*(1/n2) = 2 T(n) = O(n2). **O(n)** O(n3) for(i=0;i<n;i++) \{ for(j=0;j<i;j++) \{ for(k=0;k<j;k++) x=x+2; \} \} 解:当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i 从0取到n, 则循环共进行了: 0+(1-1)\*1/2+...+(n-1)n/2=n(n+1)(n-1)/2次 T(n) = n(n+1)(n-1)/2 = (n^3-n)/2 f(n) = n^3 所以时间复杂度为O(n^3)。 ## **五、时间复杂度常用结论** ## 访问数组中的元素是常数时间操作,或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(log n)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n^3),因为算出每个元素都需要将n对 元素相乘并加到一起,所有元素的个数是n^2。 指数时间算法通常来源于需要求出所有可能结果。例如,n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2^n)的。指数算法一般说来是太复杂了,除非n的值非常小,因为,在 这个问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题 (如著名的“巡回售货员问题” ),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况,通常应该用寻找近似最佳结果的算法替代之。 ## **六、常用排序算法的时间复杂度** ## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2MDc5MDkz_size_16_color_FFFFFF_t_70][] ![https://img-blog.csdn.net/20130920172327687?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvem9sYWxhZA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast][https_img-blog.csdn.net_20130920172327687_watermark_2_text_aHR0cDovL2Jsb2cuY3Nkbi5uZXQvem9sYWxhZA_font_5a6L5L2T_fontsize_400_fill_I0JBQkFCMA_dissolve_70_gravity_SouthEast] [Link 1]: http://blog.csdn.net/VBEND/article/details/4850672 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2MDc5MDkz_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/edd4ef66d0184e2ea578349d5e90e64c.png [https_img-blog.csdn.net_20130920172327687_watermark_2_text_aHR0cDovL2Jsb2cuY3Nkbi5uZXQvem9sYWxhZA_font_5a6L5L2T_fontsize_400_fill_I0JBQkFCMA_dissolve_70_gravity_SouthEast]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTMwOTIwMTcyMzI3Njg3P3dhdGVybWFyay8yL3RleHQvYUhSMGNEb3ZMMkpzYjJjdVkzTmtiaTV1WlhRdmVtOXNZV3hoWkE9PS9mb250LzVhNkw1TDJUL2ZvbnRzaXplLzQwMC9maWxsL0kwSkJRa0ZDTUE9PS9kaXNzb2x2ZS83MC9ncmF2aXR5L1NvdXRoRWFzdA?x-oss-process=image/format,png
相关 时间复杂度 **时间复杂度** **一、时间复杂度的定义** 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函... 以你之姓@/ 2024年04月18日 11:04/ 0 赞/ 95 阅读
相关 搞懂时间复杂度、时间复杂度 文章目录 写在前面 1、数学中的log什么意思? 2、时间复杂度 2.1、用T(n)表示程序执行次数 末蓝、/ 2023年10月08日 12:48/ 0 赞/ 81 阅读
相关 时间复杂度_空间复杂度 时间复杂度\_空间复杂度 主要说明以下3点: 1.算法效率 2.时间复杂度 3.空间复杂度 一、算法效率 算法效率分析分为两种:第一种是时间效率,第二种 朱雀/ 2023年06月29日 15:59/ 0 赞/ 199 阅读
相关 时间复杂度 转载自:[https://blog.csdn.net/itachi85/article/details/54882603][https_blog.csdn.net_itach 约定不等于承诺〃/ 2022年12月26日 08:10/ 0 赞/ 268 阅读
相关 时间复杂度 常见的时间复杂度 <table> <thead> <tr> <th>复杂度名称</th> <th>具体表示</th> </tr> </ 叁歲伎倆/ 2022年12月04日 01:11/ 0 赞/ 238 阅读
相关 时间复杂度 几种排序算法的思想很容易掌握,就是对应的时间复杂度,究其原因就是对时间复杂度是什么,如何定义计算还不知道,那么时间复杂度是如何计算的呢?请看下文。 在说 £神魔★判官ぃ/ 2022年09月17日 12:26/ 0 赞/ 222 阅读
相关 时间复杂度 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_ た 入场券/ 2022年08月28日 13:55/ 0 赞/ 199 阅读
相关 时间复杂度 时间复杂度 1. 概念 用来表示一个算法的理论上的耗时时间 2. 时间频度 一个算法中,语句执行的次数,被称为时间频度T(n) 3.时间复杂度 存在 蔚落/ 2022年03月21日 09:31/ 0 赞/ 285 阅读
相关 时间复杂度?? O(1) < O(log n) < O(n) < O(nlog n)< O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) 时间复杂度 傷城~/ 2021年10月01日 04:02/ 0 赞/ 422 阅读
相关 时间复杂度 什么是时间复杂度 > 算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函 喜欢ヅ旅行/ 2021年06月10日 20:40/ 0 赞/ 526 阅读
还没有评论,来说两句吧...