简单的算法分析和优化

简单的算法分析和优化

(1)  复杂度

为了描述一个算法的优劣，我们引入算法时间复杂度和空间复杂度的概念。

时间复杂度：一个算法主要运算的次数，用大O表示。通常表示时间复杂度时，我们只保留数量级最大的项，并忽略该项的系数。

例如某算法，赋值做了3n3+n2+8次，则认为它的时间复杂度为O(n3)；另一算法的主要运算是比较，做

了4×2n+2n4+700次，则认为它的时间复杂度为O(2n)。

当然，如果有多个字母对算法的运行时间产生很大影响，就把它们都写进表达式。如对m×n 的数组遍历的时间复杂度可以写作O(mn)。

空间复杂度：一个算法主要占用的内存空间，也用大O表示。

在实际应用时，空间的占用是需要特别注意的问题。太大的数组经常是开不出来的，即使开出来了，遍历的时间消耗也是惊人的。

(2)  常用算法的时空复杂度

1s运算次数约为5,000,000[1]。也就是说，如果把n代入复杂度的表达式，得数接近或大于5,000,000，那么会有超时的危险。

常见的数量级大小：O(1)＜O(logn)＜O(n)＜O(nlogn)＜O(n2)＜O(n3)＜O(2n)＜O(n!)

数量级	能承受的大致规模	常见算法
O(1)	任意	直接输出结果
O(logn)	任意	二分查找、快速幂
O(n)	以百万计（五六百万）	贪心算法、扫描和遍历
O(nlogn)	以十万计（三四十万）	带有分治思想的算法，如二分法
O(n2)	以千计数（两千）	枚举、动态规划
O(n3)	不到两百	动态规划
n    O(2)	24	搜索
O(n!)	10	产生全排列
O(nn)	8	暴力法破解密码

O(1)叫常数时间；O(n)、O(n2)、O(n3)、O(n4)……叫做多项式时间；O(2n)、O(3n)……叫做指数时间。

(3)  简单的优化方法

1.  时间的简单优化方法时间上的优化在于少做运算、做耗时短的运算等。有几个规律需要注意：

Ÿ  整型运算耗时远低于实型运算耗时。

Ÿ  位运算速度极快。

Ÿ  逻辑运算比四则运算快。

Ÿ  +、-、*运算都比较快（-、*比+慢一点点，可以忽略不计）。

Ÿ  /运算比+、-、*慢得多（甚至慢几十倍）。

Ÿ  取余%和除法运算速度相当。

Ÿ  调用函数要比直接计算慢（因为要入栈和出栈）。

这些规律我们可以从宏观上把握。事实上，究竟做了几步运算、几次赋值、变量在内存还是缓存等多数由编译器、系统决定。但是，少做运算（尤其在循环体、递归体中）一定能很大程度节省时间。

2.  空间的简单优化方法空间上的优化主要在于减小数组大小、降低数组维数等。常用的节省内存的方法有：压缩储存——见180页“A.7 状态压缩*”。

覆盖旧数据——例如滚动数组（见62页“(5) 使用滚动数组”）。

要注意的是，对空间的优化即使不改变复杂度，只是改变 n 的系数也是极有意义的。空间复杂度有时对时间也有影响，要想方设法进行优化。

3.  优化的原则

Ÿ  尽量不让程序做已做过的事。

Ÿ  不让程序做显然没有必要的事。

Ÿ  不要解决无用的子问题。

Ÿ  不要对结果进行无意义的引用。

---

[1] 不同资料给出的数值是不同的，不过这不要紧。在NOIP中，只要你的算法正确，就不会在运行时间上“打擦边球”。