📖 正文

计算机科学中的复杂度

这里的「复杂度」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 即 \sum_1^{100}

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

这个得出结果的过程即「算法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->\infty,2n+1 是不是就可以渐进为 2n 了~这算是一种最差的情况,除了最差还有平均、最优,最常用最差,也就是做最坏的打算。还有就是我们只关心复杂度最重要的部不考虑细节带来的影响,比如 start=1,i++。事实上,考虑了结果也一样,那么就只关心复杂度最重要的部分就好了。

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

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

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

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

(完)

🙋 评论