赞
踩
1. 常数阶
这种与问题规模的大小无关(n的多少),执行时间恒定的算法,我们称之为具有O(1)的时间复杂度,又叫常数阶。
- int sum = 0, n = 100; /*执行一次*/
- sum = (1 + n) * n / 2; /*执行一次*/
- printf("%d",sum); /*执行一次*/
2. 线性阶
下面这段代码,它的循环的时间复杂度为O(n), 因为循环体中的代码须要执行n次。
- int i;
- for(i = 0; i < n; i++){
- /*时间复杂度为O(1)的程序步骤序列*/
- }
3. 对数阶
由于每次count乘以2之后,就距离n更近了一分。 也就是说,有多少个2相乘后大于n,则会退出循环。 由2^x=n 得到x=log2(n)。 所以这个循环的时间复杂度为O(log2(n))。
- int count = 1;
- while (count < n){
- count = count * 2;
- /*时间复杂度为O(1)的程序步骤序列*/
- }
4. 平方阶
这段代码的时间复杂度为O(n^2)。
- int i, j;
- for(i = 0; i < n; i++){
- for(j = 0; j < n; j++){
- /*时间复杂度为O(1)的程序步骤序列*/
- }
循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。
- int i, j;
- for(i = 0; i < n; i++){
- for(j = i; j < n; j++){ /*注意j = i而不是0*/
- /*时间复杂度为O(1)的程序步骤序列*/
- }
- }
5、对于顺序执行的语句或者算法,总的时间复杂度等于其中最大的时间复杂度
6、对于条件判断语句,总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度
T(n)=O(f(n))
该公式中的O表示代码的执行总时间T(n)和其执行总次数f(n)成正比。这种表示法,称之为大O记法。大O记法T(n)=O(f(n)),表示随着代码执行的次数增长(减少),算法执行时间的增长率和f(n)的增长率相同,表示的是算法的渐近时间复杂度,简称时间复杂度。
我们通过下面这个例子,来看一下如何使用该公式;
- int sum = 0; //执行一次
- for (int i = 0; i < n; i++) {//执行n次
- b = 2 * i;//执行n次
- for (int j = 0; j < n; j++) {//执行n*n次
- sum += i + j;//执行n*n次
- }
- }
分析得出上面代码执行的总次数f(n) = 1 + n + n + nn + nn = 2n²+2n+1 。
因此可以推出时间复杂度T(n) = O(2n²+2n+1 )。当n趋近于无穷大时,T(n)的增长主要与n²有关系,所以我们通常也将上述代码的时间复杂度写为T(n) = O(n²);
时间复杂度的分析有一个基本的法则:四则运算法则
1、加法法则
如果算法的代码是平行增加的,则只需加上所对应的时间复杂度。
接下来通过以下例子来讲解加法法则
下面代码执行的总次数为:f(n) = 1 + n + n;所以时间复杂度为T1(n) = O(2*n + 1)。当n趋近于无穷大时,T1(n) = O(n);
- int sum = 0;//只执行一次
-
- for (int i = 0; i < n; i++) {//执行n次
- count++;//执行n次
- }
在上述的代码基础上平行增加部分代码,增加后如下所示:
增加前时间复杂度为:T1(n) = O(2n + 1),增加部分的代码执行次数f(n) = 1 + n + n + n;所以增加的代码时间复杂度T2(n) = O(3n + 1);因为代码是平行增加的所以增加后的时间复杂度T(n) = T1(n) + T2(n) = O(5*n + 2)。当n趋近于无穷大时,T(n) = O(n);
- int count = 0;//只执行一次
- int sum = 0;//只执行一次
-
- for (int i = 0; i < n; i++) {//执行n次
- count++;//执行n次
- }
- for (int j = 0; j < n; j++) {//执行n次
- sum += j;//执行n次
- sum += 2*j;//执行n次
- }
2、乘法法则
如果算法的代码增加的是循环内的嵌套或者函数的嵌套,那么就需要乘上相应的时间复杂度。
如果不能理解这句话,别着急,接着往下看,下面的例子会帮助你理解
接下来通过以下例子来讲解乘法法则
在上面已经分析过,下面的代码时间复杂度T1(n) = O(2*n + 1),也可以写成T1(n) = O(n);
- int sum = 0;//只执行一次
-
- for (int i = 0; i < n; i++) {//执行n次
- count++;//执行n次
- }
在上述的基础上我们增加部分代码,增加后如下所示;
下面增加了一个内层循环,增加的部分如果单独看,则执行了m次,但是由于是嵌套增加的,所以当外层循坏执行一次,内层循环就会执行m次。所以当外层循环执行n次时,内层循环就会执行n*m次,所以下面代码执行的总次数f(n) = 1 + n + n + nm + nm。由时间复杂度O的定义可计算出下面代码的时间复杂度T(n) = O(2nm + 2n + 1)。当n和m趋近于无穷大时,可以认为n=m,则可以写为T(n) = O(2n² + 2n + 1)。由于n和m趋近于无穷大,所以T(n)的增长主要受n²的增长影响,所以可以写为T(n) = O(n²)
- int sum = 0;//只执行一次
-
- for (int i = 0; i < n; i++) {//执行n次
- count++;//执行n次
- for (int j = 0; j < m; j++) {//执行n*m次
- count++;//执行n*m次
- }
- }
3、除法法则和减法法则
减法和除法我相信大家通过上面的讲述可以自己推导出来,我就不多写了。我把主要的思想写在下面,供大家参考
减法法则,如果是去掉算法中平行的代码,就需要减掉相应的时间复杂度。
除法法则,如果是去掉嵌套内的循环或函数,就需要除去相应的时间复杂度。
对于上述这些常见时间复杂度,它们的执行次数T(n)和问题规模n的关系如下图:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。