计算机科学中的复杂度

这里的「复杂度」The Algorithm Complexity 是指编程计算中的算法复杂度。它包括「空间复杂度」和「时间复杂度」。

• 空间复杂度「Space Complexity」是用来衡量执行这个算法所消耗的内存大小
• 时间复杂度「Time Complexity」是用来衡量执行这个算法所需要的时间长度

复杂度是算法的一个非常重要的指标，时间和空间是计算机资源最重要的参数，因此占用资源低是算法的终极目标，这直接影响了一个程序的质量和效率，时间复杂度越低，执行效率就越高。

你可以在「在线评测」Online Judge 这类网站中看到它的身影。其中加入了时间和空间的限制。参见  T^T Online Judge（www.fjutacm.com）的截图

因此选择合适的算法和优化算法来降低复杂度也是 ACM – ICPC「国际大学生程序设计竞赛」的核心竞争力之一。

复杂度分析

分析时间复杂度之前，我们先来弄懂一个概念。

在数学中，大 O 符号「Big O notation」（大写字母 O 不是零 0）是用于描述函数渐进行为的数学符号。渐进行为？！别慌，看我慢慢给你扯

嘿，你知道最基本的运算时是什么嘛？？不用怀疑，就是加减乘除呗，当然你也可以说加减甚至是加法运算。那么我们来说说加法如何~

假设现在要你从 1 累加到 100 即

很容易吧，不考虑捷径，我们暴力求解计算 100 次，如果是加到 1 000 000 呢？更多呢？嗯，现在我们求 1 到 n 的和（n>1,n∈Z）即

这个得出结果的过程即「算法」Algorithm。这个求和算法总共计算了 n 次，n 次计算其实就是「复杂度」Complexity。容易得出复杂度为线性函数，我们把它记作 O(n)，称「线性复杂度」Linear Complexity。

是不是很简单，嘿嘿，别走，还有~

写个代码吧~

int start = 1, end = n, result = 0;
for (int i = start; i <= end; i++)   //执行了n+1次
    result += i;                     //执行了n次

for 循环总共循环了 n+1 次，其中有 n 个执行了累加语句，总计 n+1+n=2n+1 次，记为 O(n)。你可能会奇怪，为什么这个复杂度不是 O(2n+1)请看下行分解

你知道极限吗？其实前面所谓的「描述函数渐进行为」就是取极限，你想下，当 n->，2n+1 是不是就可以渐进为 2n 了~这算是一种最差的情况，除了最差还有平均、最优，最常用最差，也就是做最坏的打算。还有就是我们只关心复杂度最重要的部不考虑细节带来的影响，比如 start=1，i++。事实上，考虑了结果也一样，那么就只关心复杂度最重要的部分就好了。

那么 2n 怎么变成 n 的呢？？？？？？？？？这个……我不知道~

嘿嘿，皮一下很开心~其实大 O 符号是一种算法复杂度的「相对」表示方式。相对，就是说在数据量的增加的同时耗时也在增加，而描述这个增长关系的函数就是 O 本身。既然 O(3n)和 O(n)都是表示线性复杂度，为什么不用更具有一般性的 O(n)作为代表呢?这跟分式化简一个理儿。在描述算法复杂度的时候并不是具体的描述这个复杂度，而是描述它属于哪类复杂度，是抽象的数量级。除了线性复杂度，还有常数复杂度、平方复杂度、对数复杂度、组合复杂度等……

*注意：由于使用的编程语言不尽相同，甚至相同语言不同版本，不同编译器，不同平台都可能有非常大的「空间」占用差异，因此这里的计算不讨论「空间复杂度」。相信有一定计算机基础的同学参阅官方文档都可以轻松的计算「空间复杂度」，它也是类似时间复杂度的，确实很复杂……

扩展加深阅读  http://blog.jobbole.com/55184/