很多程序员在面对算法问题时往往一筹莫展，在这里，两行哥想帮助大家一把，让大家以更快迈入算法的大门。请记住，基本的算法设计与分析，是高级程序员必备技能。
本文分为两个部分，一部分带大家理解算法中衡量算法优劣最基础的两个概念：时间复杂度和空间复杂度，另外一部分为大家介绍数学基础复习大纲。数学基础是算法研究的基石，如果你的数学已经还给老师，请尽快温习起来。
一入算法深似海，请做好持久战的准备。
一、算法的时间与空间复杂度
算法的时间复杂度和空间复杂度是衡量一个算法效率的基本方法。在阅读其他算法教程书的时候，对于算法的讲解不免有些生涩，难以理解，在这里两行哥尽量用通俗易懂的语言像大家讲解这两个算法概念，让我们以理解这两个概念作为跨入算法大门的第一步。
（一）时间复杂度
先来看看通常算法书籍中对时间频度及衍生出来的时间复杂度的定义：
（1）时间频度：一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。
（2）时间复杂度：在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n))，称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
看到这种概念式的讲解立刻就感到昏昏欲睡，让我们忘记上面的概念，来看一个简单的例子：
public void getSum() {
int sum = 0;//执行了1次
int n = 100;//执行了1次
for (int i = 0; i < n; i++) {//执行了n + 1次。为啥需要 + 1？请读者自己思考
sum += i;//执行了n次
}
System.out.println(sum);//执行了1次
}
这里备注了每一行代码的执行次数，上述代码一共执行了1 + 1 + （ n + 1） + n + 1次，即2n + 4次。
上述算法语句执行的总次数为2n + 4次，而当 n 不断增大，比如我们这次所要计算的不是 1 + 2 + 3 + 4 + ...... + 100 = ？ 而是 1 + 2 + 3 + 4 + ...... + n = ？，其中 n 是十分大的数字，那么由此可见，上述算法的执行总次数（所需时间）会随着 n 的增大而增加，但是在 for 循环以外的语句并不受 n 的规模影响（永远都只执行一次）。所以我们可以将上述算法的执行总次数简单的记作：
2n或简记为n（为什么简记为n？下文分析）
这样我们就得到了上文计算 1 + 2 + 3 + 4 + ...... + 100 = ？的算法的时间复杂度，我们把它记作：
O(n)
对于同一个问题，解法通常是不唯一的。比如 1 + 2 + 3 + 4 + ...... + 100 = ？这个问题，还有其他的算法，比如我们使用高斯算法：
SUM = 1 + 2 + 3 + 4 + ...... + 100
SUM = 100 + 99 + 98 + 97 + ...... + 1
SUM + SUM = 2 * SUM = 101 + 101 + 101 + .... + 101
SUM = （100 * 101） / 2 = 5050
代码实现为：
public void getSum() {
int n = 100;//执行1次
int sum = (1 + n) * n / 2;//执行1次
System.out.println(sum);//执行1次
}
此时算法的时间复杂度为：
O(3)或简记为O(1)
从感官上我们就不难看出，从算法的效率上看，当n足够大时，O(3) < O(n) ，所以高斯算法更快，更优秀。
这种用个大写的O来代表算法的时间复杂度的记法有个专业的名字叫“大O阶”记法。那么通过对上述的例子进行总结，我们给出算法的时间复杂度（大O阶）的计算方法：
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项。
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。
这也就解释了上文将O(2n)简记为O(n)或将O(3)简记为O(1)的原因。让我们再用一个例子来练习“大O阶” 法计算算法的时间复杂度：
public void doSomething() {
int n = 100000;//执行1次
for (int i = 0; i < n; i++) {//执行n+1次
for (int j = 0; j < n; j++) {//执行n * (n+1)次
System.out.println(i + "=" + j);//执行n * n次
}
}
for (int i = 0; i < n; i++) {//执行n+1次
System.out.println(i);//执行n次
}
System.out.println("finish");//执行1次
}
上面的代码严格说不能称之为一个算法，毕竟它很“无聊而且莫名其妙”，先不论这个“算法”能解决什么问题，我们看一下它的“大O阶”如何推导，还是先计算一下它的执行总次数：
执行总次数 = 1 + (n + 1) + n * (n + 1) + n * n + (n + 1) + 1 = 2n^2 + 3n + 3
1.用常数1取代运行时间中的所有加法常数：
执行总次数 = 2n^2 + 3n + 1
2.在修改后的运行次数函数中，只保留最高阶项：
执行总次数 = 2n^2
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数：
执行总次数 = n^2
最后得到上述代码的算法时间复杂度表示为：O(n^2)
至此，我们对什么是“算法的时间复杂度”和“算法的时间复杂度”表示法“大O阶”的推导方法进行了简单的说明。我们在把常见的算法时间复杂度以及他们在效率上的高低顺序记录在这里，是大家对算法的效率有个直观的认识。
O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) 立方阶< { O(2^n) < O(n!) < O(n^n) }
最后三项用大括号括起来是想要告诉读者，如果日后设计的算法推导出的“大O阶”是大括号中的这几位，那么趁早放弃这个算法，去研究新的算法吧。因为大括号中的这几位即便是在n的规模比较小的情况下仍然要耗费大量的时间，算法的时间复杂度大的离谱，基本上就是“不可用状态”。
注意：
为了方便读者理解，上文的很多说法不够严谨，其实使用执行语句数描述算法的时间复杂度是不够全面的，因为执行语句数与编程语言有关，也与程序员个人编码风格有关。同时也忽略了每行代码的执行时间（比如，浮点数运算比整数型运算慢的多，对于2n行的整数型运算和n行的浮点运算，哪个更快呢？），这里只是粗略地抽象出了衡量算法优劣的简单模型，除了大O法（衡量算法时间复杂度上限），还有其他一些方法，比如Ω法（衡量算法时间复杂度下线）等，日后大家都可能接触到。
也许有读者有疑问，为什么在“修改后的运行次数函数中，只保留最高阶项”这样近似地求解算法的时间复杂度的？
这里涉及到增长率问题（近似于数学中的导数、直线斜率）。对于一个给定的函数，我们为了方便计算，忽略了相对微不足道的低阶因变量（当且仅当输入规模n足够大）。例如，当n足够大时：n^4 + 2n^2 + 100n + 500 约等于 n^4。
常用增长率从大到小排序：
常用增长率比较
（二）空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括：
1.存储算法本身所占用的存储空间；
对于1而言，存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。
2.算法的输入输出数据所占用的存储空间；
对于2而言，算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。
3.算法在运行过程中临时占用的存储空间。
对于3而言，算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元。
第1点和第2点被称为静态空间，主要包括指令空间（即代码空间）、数据空间（常量、简单变量）、输入输出数据等所占的空间。
第3点被称为动态空间，主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法实现方式有关。因此，第3点是我们对算法空间复杂度的主要衡量点。
让我们来看一段代码：
public void reserse(int[] a, int[] b) {
int n = a.length;
for (int i = 0; i < n; i++) {
b[i] = a[n - 1 - i];
}
}
上方的代码中，当程序调用 reserse() 方法时，要分配的内存空间包括：引用a、引用b、局部变量n、局部变量i，因此 f(n)=4，4为常量，所以该算法的空间复杂度 S(n)=O(1) 。
如一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n)。若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。
（三）时间与空间复杂度关系
算法的时间复杂度和空间复杂度合称为算法的复杂度。对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。
当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使 时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法（特别是大型算法）时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。
二、学习算法的数学基础准备
很多读者可能在大学毕业后就将数学抛掷脑后了，面对满屏的数学符号，瞬间就会感到头疼。问题来了，如果我们已经好久不接触数学，该如何把数学重新捡起来呢？大部分程序员不需要高深的数学功底，更重要的是基础数学要学的扎实。
打好数学基础只需要下面五样：
1.笔
2.纸
3.初等数学教材（高中数学教材）一套
4.高等数学教材（大学数学教材）一套
5.能连接互联网的PC
而上述五样中，最重要的是前三样，一定要动笔在纸上写写画画。在业务相关的大部分算法中，初等数学就能解决很多问题，所以重中之重依然是初等数学。
那么初等数学中哪些知识点需要重新巩固学习呢？
0.基本数学运算
初等数学涉及的各种数学运算及含义，如：
（1）函数，如：指数函数、对数函数、幂函数、三角函数
（2）基本几何，如：直线方程、圆方程
（3）三角函数与三角变换
（4）向量
（5）数列
（6）逻辑与判断
（7）概率与统计
（8）导数
对于第0点而言，不知道怎么补怎么办？很简单，两行哥告诉你，淘宝买一套人教版高中数学就好了！
为什么用0作为起始编号？因为0是基础中的基础，没有0就没有后面的123。
不要以为复习高中数学对于程序员来说是在浪费时间！基础越牢，走的越远！
1.向量与矩阵
（1）向量概念与几何含义
（2）向量基本运算
（3）向量空间
（4）矩阵概念与几何含义
（5）矩阵基本运算
（7）逆矩阵含义与性质
2.线性方程组
（1）线性方程组的解
（2）矩阵的初等变换
（3）矩阵的秩
（4）矩阵特征值与特征向量及其几何意义
3.图形变换（图形学算法）
（1）图形矩阵表示
（2）图形变换与矩阵变换
（3）基本矩阵变换（平移、缩放、旋转、翻折、错切）
（4）组合变换
对于上述三点如何补习呢？可以参考教材《计算机数学：算法基础 线性代数与图论》 [人民邮电出版社]。不过这本书有一定错误，需要读者仔细阅读，带着头脑去阅读，尽信书不如无书。
还有什么可以帮助大家锻炼计算机数学的书籍呢？入门级的首推《程序员的数学》[人民邮电出版社]，还有一本有深度的大书也可以尝试阅读《数学之美》[人民邮电出版社]。
关于两行哥算法系列的序，就和大家聊到这里，希望各位读者能找到自己的学习方法，当你真正接触到算法，才会发现数学思维对编程的影响有多大。仰望数学之美。
网友评论