如何计算算法的时间复杂度和空间复杂度,怎么计算算法时间复杂度

　　Yyds干货库存

　　目录

　　分析算法时间复杂度的基本方法

　　例子

　　算法时间复杂度计算

　　算法空间复杂度

　　算法1

　　算法2

　　分析算法时间复杂度的基本方法1。找出出现频率最高的句子作为基础句。

　　2.计算基本句的出现频率得到一个问题规模n的函数f(n)

　　3.取其数量级，用符号“O”表示。

　　示例分析了以下程序段的时间复杂度

　　I=1；//

　　while(i=n)

　　I=I * 2；//关键是找出执行次数x和n之间的关系，用称为n的函数表示：

　　如果循环执行一次：i=1*2=2，

　　如果循环执行两次：I=2 * 2=2 ^ 2，

　　如果循环执行三次：I=2 * 2 * 2=2 ^ 3，

　　如果循环执行x次：I=2 * 2 *.=2 x，

　　设语句执行x次，可以从循环条件i=n，2 x=n得到，所以x=log2n。

　　即f(n)log2n，最大值f(n)=log2n，所以这个程序段的时间复杂度T(n)=O(log2n)。

　　请注意算法时间复杂度的计算：在某些情况下，算法中基本运算的重复次数会随着问题的输入和数据集的不同而不同。

　　比如顺序搜索，在数组a[i]中找到值等于E的元素并返回其位置。

　　for(I=0；I n；我)

　　if(a[i]==e)返回I 1；//找到，返回哪个元素？

　　返回0；

　　最佳情况：1次

　　最坏情况：n次

　　平均时间复杂度为：O(n)

　　算法空间复杂度算法1 for(I=0；i i ) {

　　t=a[I]；

　　a[I]=a[n-I-1]；

　　a[n-I-1]=t；

　　}只创建了一个额外的测试变量，

　　S(n)=O(1)，原地工作。

　　算法2 for(I=0；I n；我)

　　b[I]=a[n-I-1]；

　　for(I=0；I n；我

　　a[I]=b[I]；产生了额外的b[i]，所以S(n)=O(n)。

　　原创作品来自秃弱博主，转载请联系作者获得转载授权，否则将追究法律责任。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。