写点什么

算法—算法的时间空间复杂度

发布于: 10 小时前

1. 事后分析法

缺点:不同的数据规模,不同的机器下算法运行的时间不同,无法做到计算运行时间

2. 事前分析法

2.1 大 O 时间复杂度

渐进时间复杂度 随着 n 的增长,程序运行时间跟随 n 变化的趋势

2.1.1 几个原则

去掉常数项


2(n^2) =n^2


一段代码取时间复杂度最高的


test(n) {  //时间复杂度n^3 for(int i = 0; i < n ; i++){   for(int i = 0; i < n ; i++){     for(int i = 0; i < n ; i++){            print(n);     }   } } //时间复杂度n^2 for(int i = 0; i < n ; i++){   for(int i = 0; i < n ; i++){     print(n);   } } //时间复杂度n for(int i = 0; i < n ; i++){   print(n); }}
复制代码


这段代码的时间复杂度为 n^3+n^2+n


当 n 足够大时,n^2 和 n 与 n^3 相比太小,可以忽略不计

2.1.2 常见复杂度

o(1)


i = i + 1;
复制代码


o(n)


test(n){  for(int i = 0 ;i < n;i++){    print(i);  }}
复制代码


o(n^2)


test(n){  for(int i = 0 ;i < n;i++){    print(i);    for(int j = 0 ;j < n;j++){      print(i);    }  }}
复制代码


o(log2n)


PS:如果 ax =N(a>0,且 a≠1),那么数 x 叫做以 a 为底 N 的对数,记作 x=logaN,读作以 a 为底 N 的,其中 a 叫做对数的底数,N 叫做真数。


test(n) {  int i = 1;  while (i <= n) {    i = 2 * i;  }}
复制代码


随着循环次数的增加,i 的值变化如下



根据对数函数的公式 2 的 i 次方等于 n,i 等于 log2n


2.2 最好情况时间复杂度

数据比较有序的情况的时间复杂度

2.3 最坏情况时间复杂度

数据完全无序

3. 空间复杂度

与 n 无关的代码空间复杂度可以忽略


空间复杂度 O(n)


test(n) {  //在内存中开辟了一个长度为n的数组  List array  =  List(n);  print(array.length);}
复制代码




发布于: 10 小时前阅读数: 3
用户头像

还未添加个人签名 2019.10.04 加入

微信公众号:思想者杰克

评论

发布
暂无评论
算法—算法的时间空间复杂度