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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法——算法的时间与空间复杂度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1235字，纯文字阅读大概需要2分钟。

内容图文

算法的时间与空间复杂度

事后分析法

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

事前分析法

大O时间复杂度

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

几个原则

去掉常数项

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相比太小，可以忽略不计

常见复杂度

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

最好情况时间复杂度

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

最坏情况时间复杂度

数据完全无序

空间复杂度

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

空间复杂度O(n)

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

内容总结

以上是互联网集市为您收集整理的算法——算法的时间与空间复杂度全部内容，希望文章能够帮你解决算法——算法的时间与空间复杂度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---