草丁图书馆

  1. 首页 > 生活杂烩 >

时间复杂度怎么算，复合函数的时间复杂度怎么算( 二 )

小知识


则有f（n）= n的三次方，然后根据T（n）/f（n）求极限可得到常数c
则该算法的 时间复杂度：T（n）=O（n^3） 注：n^3即是n的3次方 。
3.在pascal中比较容易理解，容易计算的方法是：看看有几重for循环，只有一重则时间复杂度为O（n）,二重则为O（n^2），依此类推，如果有二分则为O(logn)，二分例如快速幂、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn) 。

分类
按数量级递增排列，常见的时间复杂度有：
常数阶O(1),对数阶O(log2n),线性阶O(n),
线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，
k次方阶O(n^k), 指数阶O(2^n) 。 随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低 。

关于对其的理解
《数据结构（C语言版）》------严蔚敏 吴伟民编著 第15页有句话"整个算法的执行时间与基本操作重复执行的次数成正比 。 "
基本操作重复执行的次数是问题规模n的某个函数f(n)，于是算法的时间量度可以记为：T(n) = O( f(n) )
如果按照这么推断，T(n)应该表示的是算法的时间量度，也就是算法执行的时间 。
而该页对“语句频度”也有定义：指的是该语句重复执行的次数 。
如果是基本操作所在语句重复执行的次数，那么就该是f(n) 。
上边的n都表示的问题规模 。

以下来自百度知道：

对于这些算法
(1) for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s++;

(2) for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
s++;

(3) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
s++;

(4) i=1;k=0;
while(i<=n-1){
k+=10*i;
i++;
}

(5) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;

对应的时间复杂度为：

1.时间复杂度O(n^2)
2.时间复杂度O(n^2)
3.时间复杂度O(n^2)
4.时间复杂度O(n)
5.时间复杂度O(n^3)

一般来说，时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)
比如：一般总运算次数表达式类似于这样：
a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f
a<>0时，时间复杂度就是O(2^n);
a=0,b<>0 =>O(n^3);
a,b=0,c<>0 =>O(n^2)依此类推

那么，总运算次数又是如何计算出的呢？
一般来说，我们经常使用for循环，就像刚才五个题，我们就以它们为例
1.循环了n*n次，当然是O(n^2)
2.循环了(n+n-1+n-2+...+1)≈(n^2)/2，因为时间复杂度是不考虑系数的，所以也是O(n^2)
3.循环了(1+2+3+...+n)≈(n^2)/2,当然也是O(n^2)
4.循环了n-1≈n次，所以是O(n)
5.循环了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6(这个公式要记住哦)≈(n^3)/3，不考虑系数，自然是O(n^3)

另外，在时间复杂度中，log(2,n)(以2为底)与lg(n)(以10为底)是等价的，因为对数换底公式：
log(a,b)=log(c,b)/log(c,a)
所以，log(2,n)=log(2,10)*lg(n),忽略掉系数，二者当然是等价的
如何计算时间复杂度 简单理解，时间复杂度就是执行语句被调用了多少次 。 (1)如果只调用了一次，如： x=5; if(x<-4) {x=x+4;} else {x=x+3;} 在大括号中的内容，只会调用一个语句，那么O(n)=1; (2)如果调用了两次，如： x=5; if(x<-4) {x=x+4;} else {x=x+3;} x=x+56; 在大括号中的内容，只会调用一个语句，但是在最后，还有一个计算公式要调用语句；总共加起来就是调用2次 。 那么O(n)=2; （3）用1个FOR循环调用 for(x=0;x
求怎么算时间复杂度 基本操作是S的累加,设基本操作时间为C,忽略初始化S的时间和循环变量i,j累加的时间,基本操作总次数是n*n(n的平方);所以算法运行时间为T[n]=C*n*n.
时间复杂度实际上就是基本操作语句的频度 。
本题中的基本操作语句是 s++;
显然它一共执行了 n*n 次，
所以本题的时间复杂度是 o(n*n) 。

推荐阅读


上一篇：曲面屏怎么贴膜，如何贴曲面屏钢化膜

下一篇：退团怎么退，不想当团员了怎么退团