1.2.1算法的定义

一堆指令放在一起，去做一件事情。而这个指令集一定是有限的。

无论如何，一定会产生至少一个输出。否则算法就没有意义了。

有些程序可以一直跑，比如操作系统，只要不关机，就一直跑。

在描述一个算法的时候，它是不能有这种无线循环的概念的。

目标不可以太远大。

描述应该抽象。

案例:选择排序算法的伪码描述

这里像C语言，但又不是。因为它中间两个最核心的步骤，是用自然语言来描述的。

选择排序是从还没有排好序的这堆元素中间，每次选一个最小的元素，把它贴到已经排好序的那个子序列的最后面，于是每次挑一个最小的贴上去，每次挑一个最小的贴上去，最后得到的就是一个从小到大排好序的序列，从List[i]到List[N-1]中找到最小元。

那就意味着没排好序的子序列放在哪里呢？放在从List[i]一直放到List[N-1]。

隐含的也就是说，排好序的部分是放在哪里呢？放在List[0]一直到List[i-1]这个位置。

那么我们从没排好序的这一部分中间找一个最小元，然后我们记录下它的位置，变量叫MinPosition，然后把这个位置的这个变量，换到有序部分的最后位置。

比如说哪是”有序部分?最后位置?”上图写的都不是很清楚。

这里换一个比较清楚的伪代码表示。

这里的List[i]就是有序部分的最后位置，上面这段代码描述一个很重要的特点是:抽象。

这个list无论是数组还是链表，算法依然正确。

在描述算法的时候，其实并不关心swap具体的实现方式(函数/宏)。

1.2.2什么是好的算法

解决同一个问题的时候，我们通常会有多种不一样的算法，区别就在于，有的算法比较笨，有的算法比较聪明，那如何衡量谁好谁坏呢？通常有下面两个指标。

空间/时间复杂度

一个指标是”空间复杂度”，记成S(n)，就是”Space”。

另一个指标是”时间复杂度”，记成T(n)，也就是”Time”。

为什么要把这两个指标写成是一个n的函数呢？因为这两个指标，其实跟我们要处理的数据规模的直接相关的。

举个例子，如果打印10个整数，那么程序可能瞬间就给出结果了，如果打印10W个整数，可能就需要等一会了。

所以这个程序运行的时间，跟要处理的数据是10个还是10W个相关的。

这个10或者10W，就是要处理的数据的规模。

把这个数据的规模叫做n，是一个变量的话，那么这个程序所用的时间和空间都跟这个n有直接关系。

当然了，解决一个问题有很多种方法，在设计这个地方的时候，一定要把这两个因素考虑清楚，一不小心，如果空间复杂度太大的话，那么程序可能就直接爆掉，非正常中断，如果时间复杂度太大的话，那么可能等了很长时间都不出结果。

案例:递归(线性增长)

假设在内存里有这么一块空间，是这个程序可以用的。

开始调用这个PrintN，然后把100000作为参数传给它，

这个时候，程序做了一件什么事呢？

于是它递归调用PrintN，传进去参数99999，

在调用这个函数之前，我的系统会把当前这个函数所有现有的状态都存到系统内存的某一个地方，而是说这块内存是为了PrintN(100000)这个程序而存储的，把它当前的状态存下来，然后再去执行PrintN(N-1)这个函数。

执行完了之后，系统会把这些存储的状态再恢复回来，接着执行这个函数的下一句。

因为它是个递归调用，于是这个情况就变成了什么？

下一步我们要调用PrintN(99999)，然后进去以后，我们发现先调用PrintN(99998)。

于是这个程序所有的变量都要被存一下。

一直到最后什么时候可以返回了呢？到我们调用PrintN(0)的时候，可以返回。

那么在调用PrintN(0)之前呢，必定调用了PrintN(1)。

所以最后存在系统里的一块内容，应该是PrintN(1)这个函数所有的当前的状态。

于是我们就发现，它在内存里占用的空间的数量，实际上是跟我们这个原始的N的大小成正比的。

也就是说，空间复杂度作为一个N的函数的话，是一个常数乘以N，

也就是说，随着N来做线性增长，

当这个N非常非常大的时候，你的程序可以用的空间是非常有限的，它把它有限的空间用爆掉了，所以它就非正常退出了。

案例:循环(空间固定)

让N继续变大，在这个循环程序里，它只用了临时变量和一个for循环，它没有涉及到任何程序调用的问题，不管这个N有多大，它占用的空间始终都是一个固定的，它占用的空间的量不是随着N的增长而增长，所以它的空间占用始终是一个常量，即:”这个是永远没问题的”。

案例:多项式求值(加减乘除)

在之前测试了一下，发现第二个函数比第一个函数快很多，具体为啥呢？

在分析一个函数运行效率的时候，在一个这么简单的函数中，因为只有加减乘除。

机器运算加减法的速度比乘除法的速度要快得多，所以我们基本上就是在数函数到底做了多少次乘除法，(在某个程度上)加减法可以忽略不计。

那么现在数一下，它到底做了多少次乘法。

第一个函数，它的时间复杂度作为n的函数，是一个常数乘以n平方，加上一个常数除以n。

而对第二个函数，它的时间复杂度应该就是一个常数乘以n。

那么常数C1、C2、C到底是什么，其实每台机器跑起来可能都不太一样。

但是不管这三个常数是什么，我们知道当n充分大的时候，n平方，其实是远远的超过了n的，这就意味着，当n很大的时候，第二个程序一定会比第一个程序快很多的。

可以多试几个数值跑几次。

最坏情况/平均复杂度

其实在分析的时候，比较喜欢分析的是这个最坏情况复杂度，”平均复杂度会小于最坏复杂度”，因为”平均复杂度”经常不是一个容易搞定的问题，所以呢，分析这个平均复杂度会非常难。

小总结(复杂度)

1.2.3复杂度的渐进表示

当我们在分析一个算法复杂度的时候，我们是没必要一步步去数，把哪个操作做了多少次的。

其实我们关心的是，随着要处理的数据规模的增大，它这个复杂度增长的性质会怎么样？

比如说，当比较上述两个算法的时候，我们只要知道:

第一个算法，它的时间复杂度当n很大的时候，基本上就是n平方在起作用的。

第二个算法，它的时间复杂度当n很大的时候，是n在起主要作用的。

所以比较n平方和n，当n充分大的时候，那么第一个算法肯定要比第二个算法要慢的。

知道这点就足够了。

即:我们从来不对算法做非常精细的分析，只粗略的知道它的一个增长趋势就可以了，于是就有了复杂度的”渐进表示法”。

上图解释

我们如果把一个时间复杂度写成T(n)写成一个O(f(n))的形式，f(n)大概表现的是T(n)的上界，

简单地来说，O(f(n))就表示f(n)是T(n)的某种上界。

对于充分大的n而言，那么这个g(n)就是T(n)的某种下界。

简单地来说，Ω欧米伽(g(n))就表示g(n)是T(n)的某种下界。

如果看到大Θsita，那就表示对于这个Θ里面的函数来说，O和Ω是同时成立的，也就是说，它既是上界也是下界，它们基本上是等价的。

贴近真实情况(粗略->趋势)

那么，说到这里要注意一个问题。

当我们在讨论O和Ω，也就是上界和下界的时候，我们要注意，一个函数的上界和下界不是唯一的，联系到实际的数学，它可以有无穷多个。

比如说我们的一个算法的复杂度是n的常数倍，那么我可以把它写成是O(n)的，也可以把它写成是O(n^2)的，也可以把它写成是O(n^3)的，等等，可以有无穷种写法。

当然下界也是一样。

但是太大的上界和太小的下界，对我们分析一个算法的效率而言，是没有什么帮助的。

我们分析算法效率的时候，总归是希望，不管是上界还是下界，都尽可能地跟它的真实情况贴的越近越好。

所以，我们在写O(n)的时候，我们一般取得是能找到的、最小的那个上界。

当我们在写Ω(n)的时候，我们一般取得是能找到的、最大的那个下界。

输入规模

这里增加一下对不同复杂度函数的感性理解。

这张表显示了不同的函数随着n的增长，它的增长速度。

这个第一行给出的是输入的规模n，n从1、2、4、8、16涨到32，要注意到n还很小，最大才只是32而已。

(第1行)我们的函数第一个是”常函数”，常函数就是一个常数嘛，我们就用1作为它的代表，它既然是常数，所以不管n是多少，它始终都是1，都是常数。

(第2行)第二行给的是logn，我们看到logn 它的增长是非常缓慢的，当n涨到32的时候，它也就涨到5而已，顺便说，这个logn看上去应该是以2为底的，实际上呢，它到底是以2/10/e为底，其实是没关系的，不管是以什么为底它都只是差一个常数倍而已，所以很多教科书上写logn的时候，就写一个”logn”，不写它的底，因为无关紧要。

(第3行)第三行的n是随着n的增长而增长。

(第4行、第5行、第6行)nlogn、n2、n3，可以发现n3还不是最可怕的。

(第7行)2的N次方，当n才只是32的时候已经非常大了

(第8行)更可怕的是n!阶乘。

所以在设计算法的时候，千万不要设计出来一个复杂度是n!阶乘的算法，再看一下，n还是很小的时候，n!阶乘已经很大了！

这张图，显示了各种不同的函数，它的增长的速率。

我们知道logn是最好的函数，logn涨的是最慢的，

比它稍微慢一点的是n，

居于n和n平方时间的是n倍的logn。

顺便说，作为一个专业的程序猿，在设计算法的时候，当看到一个算法的复杂度是n平方的时候，那么要下意识的、本能的反应，有没有办法把它降到nlogn，如果能降到nlogn，那么效率的提升是非常明显的。

比如，当n等于100W的时候，n2的值就会很大，而logn的值相对来说，其实是一个非常小的值了，所以会差很多很多倍。

这个表格:给了一个具体的时间，可以让体会更深一些。

第一列给出的是n的变化，n从10一直变到100W，然后每一列对应一个复杂度的函数，

当n=100的时候，你的程序就不要想着跑出结果了。

复杂度分析小窍门

比如说，如果我们有两段算法，我们知道它们复杂度的上界是什么。

如果把两段算法放在一起的时候，总时间就是两段的和。

那么它们的上界，就是两个中比较大的那个。

当把两段算法嵌套起来的时候，两个复杂度要相乘的时候，它的上界就是它们的乘机。

如果T(n)是关于n的一个k阶多项式的话，那么，真正起作用的就只有最大的那一项，其他的所有项都是可以忽略不计的。

这里的for和if-else略。

小总结