算法入门到精通系列2之算法复杂度（一）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法入门到精通系列2之算法复杂度（一），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2600字，纯文字阅读大概需要4分钟。

内容图文

算法入门到精通系列2之算法复杂度（一）

#杨景文算法系列

一、概述

算法复杂度又分为时间复杂度和空间复杂度。本节主要是介绍时间复杂度。时间复杂度表示计算机执行一段算法所需要的时间。对于计算机来说，解决同一个问题不同的算法，所需时间越少的算法越优（不考虑空间问题），所以时间复杂度是衡量一个算法好坏的指标之一。

二、大O符号

衡量时间复杂度通常使用”大O符号“。什么是大O符号？我们需要先看看一些数学知识：函数和极限。

2.1、数学举例：

1、一元二次函数f(x)=2x^2+2x+2;
2、当x趋于无穷大的时候，记作x—>∞。
3、x->∞，f(x)=2x^2+2x+2=2x ^2。
上述第3项，当x无穷大的时候2x^ 2+2x+2约等于2x ^ 2，在极限思想（算法分析）里面可以理解为2x^ 2+2x+2=2x^2。原因如下：
当x=5的时候：
2x^2+2x+2=62.
2x^2=50.
当x=500的时候：
2x^2+2x+2=501002
2x^2=250000.
通过上面的例子，继续增大x的值，甚至无穷大的时候，f(x)函数中的2x+2这一项就可以忽略不计了。所以x->∞时，（2x^ 2+2x+2）约等（2x^ 2），或者（2x ^ 2+2x+2）=（2x ^ 2）。并且在极限思想里面，2x ^ 2前面的系数2也是可以省略的。也就是说x->∞的时候，2x ^ 2~x^2。
通过极限的思想，我们将函数f(x)=2x^ 2+2x+2，省略剩余项为x^ 2。也就是说x->∞时，f(x)=2x^ 2+2x+2=x^ 2；使用大O符号表示：x->无穷大，f(x)=O(x^2)。

2.2、概念

大O是用来刻画被截断的无穷级数尤其是渐近级数的剩余项。大O符号表示函数的渐进性上界。就好比上面的数学举例，函数f(x)=2x ^ 2+2x+2 渐进级数的剩余项就是x^ 2，记作O(x^ 2)。也就是说O(x^2)是f(x)的渐进性上界。

三、时间复杂度

题目：求1+2+3+……+n的和。（高斯算法）

• 初级程序员的代码：

… …
    for (int i = 1; i <= n; i++) {
        sum+=i;
    }
… …

分析：
1、上述代码中的sum+=1执行多少次？ 答案：n次。
2、int i=1执行1次。
3、i<=n执行n+1次。（因为for循环执行的顺序，只有i大于n时才会停止循环，所以i=n+1的时候，还会再判断一下i<=n，所以相比较而言会多执行一次）。
4、i++执行n次。
汇总一下，上述代码执行n+1+n+1+n=3n+2次。
如果用极限思维，n->∞，3n+2 ~ 3n ~ n；记作O(n)。O(n)就是上述代码的时间复杂度。

• 高级程序员的代码：

… …
(1+n)*n/2
… …

如上，同样的计算1加到n，采用高斯算法就简单多了。上述代码只需要执行1次，没有循环。所以时间复杂度就是O(1)。

• 小结
  O(1)和O(n)的区别是什么呢？当上述”初级程序员代码“和”高级程序员代码”中的变量n不断增大的时候，高斯算法的时间复杂度基本不变，还是O(1)。但是“初级程序员代码”的时间复杂度就会增加。
  对于计算机来说，高斯算法求解1连续加到n的计算速度远远大于for循环的速度。速度越快，系统的性能就会越好。
  

总结

1、O(1)和O(n)都是时间复杂度的表示法。简单理解1代表一个单位时间，n代表n个单位时间。
2、因为计算机硬件的不同，同样的一个算法可能时间是不一样的，但是在同样硬件的计算机上执行同样的算法的时间复杂度是一样的，因为硬件不同导致的时间区别，所以常用“单位时间”这个词，而不是具体的1s或者2s。
3、时间复杂度的计算用到的符号和概念涉及到数学的函数和极限的知识点，如果忘记的同学，可以复习一下。

内容总结

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

内容备注

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

内容手机端

---