草丁图书馆

  1. 首页 > 生活杂烩 >

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

小知识



5|||以sum＋＋为基本操作，是O(n~2)(n的平方)，因为sum++要执行n*n次，同理下一个则是O(n)，因为只需要执行A[k]=k语句n次；|||O(n^2)+O(n),很显然...|||O(n^2)+O(n)//前一个是两重循环下的基本操作就是O(n^2)，后面单循环的基本操作O(n)|||复杂度应为O(n^2);
多项式复杂度当然是取次数最大的拉,n足够大时,n^2>>n, O(n)当然忽略不计.
时间复杂度怎么算 一般情况下，算法的基本操作重复执行的次数是模块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）） 。

时间复杂度的概念：
时间复杂度是总运算次数表达式中受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)依此类推


程序中的时间复杂度是怎么计算的？ 简单理解，时间复杂度就是执行语句被调用了多少次 。
(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<n;x++)
{x=x+1;}
x会从0到n-1循环，执行的语句就是将当前x值加入新的x中，总共调用n次；那么O(n)=n;
(4）用2个嵌套FOR循环调用
for(x=0;x<n;x++)
{
for(y=1;y<=n;y++)
{x=x+y;}
}
遇到嵌套循环，可以先将外面的FOR语句中的变量固定为初始值x=0，主要看里面的FOR语句的时间复杂度，很明显，里面语句执行次数是从1到n总共调用n次，O(n)=n；这还只是x=0时的调用 。 x可以从0到n-1，共n次 。 每次调用都会执行n次调用y的情况，因此，执行语句x=x+y；总共会调用n*n次 。 O(n)=n^2 。

数执行语句的执行次数，就是时间复杂度 。 注意：
(1)找到正确的执行语句 。
(2)for循环中的初始值和终止值 。
for(i=0;i<n;i++) i值变化是从0到n-1，共n次 。
for(i=0;i<=n;i++) i值变化是从0到n，共n+1次 。
(3)注意for循环的调用顺序，从里面到外面进行的 。
怎样算时间复杂度？ 求解算法的时间复杂度的具体步骤是：
⑴ 找出算法中的基本语句；
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体 。
⑵ 计算基本语句的执行次数的数量级；
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数 。 这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率 。
⑶ 用大Ο记号表示算法的时间性能 。
将基本语句执行次数的数量级放入大Ο记号中 。
如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加 。 例如：

推荐阅读


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

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