算法（Algorithm）是对特定问题的解题步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。简单说来，算法就是求解问题的步骤。

“Algorithm+Data Structures=Programs（算法+数据结构=程序）”是瑞士计算机科学家尼古拉斯·沃斯在1984年获得图灵奖的一句话。简单解释一下，数据结构表示“如何用数据正确的描述现实世界的问题，并存入计算机”，而算法表示“如何高效的处理这些数据，以解决实际问题。”

• 将一串数字 “2 1 3 5 4”按照升序排列。
  step1: 扫描5个元素，找到最小的数字，插入到第1个位置。
  step2: 扫描余下的4个元素，找到最小的数字，插入到第2个位置。
  step3: 扫描余下的3个元素，找到最小的数字，插入到第3个位置。
  step4: 扫描余下的2个元素，找到最小的一个数字，插入到第4个位置。
  至此五个元素全部放到了该放的位置上去。

  
  

  这就是从小到大排列数字的一个算法。

一个算法必须在执行有穷步骤之后结束，且每一步都要在有穷的时间内完成。这里徐需要注意的是，算法是有穷的，但是程序可以是无穷的。写过代码的都知道，当我们打开一个程序，只要不关闭，它是可以一直运行下去的。 算法中每条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现 一个算法有0个或多个输入，这些输入取自某个特定对象的集合。一个算法可以没有输入，比如单纯的向屏幕上输出一个“Hello world”。这里的特定对象，主要指的是数据对象，从数据对象中取出数据，丢给算法让它去处理。 一个算法可以有1个或多个输出，这些输出必须是与输入有着某种特定关系的量。

算法应该能够正确的解决问题。 算法应该具有良好的可读性。我们可以用自然语言描述算法、用伪代码去描述算法、可以用计算机语言去描述算法。描述算法的方式有很多，但是这个算法最好容易让人理解。 输入非法数据的时候，算法能够恰当的做出反应或进行处理，而不是会输出一些莫名其妙的结果。写程序的时候最容易出现的问题就是输入一些临界值或者非法值的时候，会输出一些莫名其妙的东西。这些东西最好要避免掉。 用接下来将要介绍到的概念来说就是，时间复杂度和空间复杂度都要低。

我们如何去评估一个算法在执行时候的时间开销呢？很容易想到的就是，让这个程序现在计算机里面去运行一下，来记录一下时间。诚然，这种方确实很简单，教材上还给起了一个名字，叫事后统计法。但是也存在一个问题，用这种方法测试出来的结果和测试的计算机的性能之间有着密不可分的关系。在性能好的计算机上运行的时间肯定短，在性能不好的计算机上运行的时间肯定长。另外，用不同的语言写出来的算法在执行时间上也会有不同，比如同样的算法，用C写出来的程序执行效率肯定比Java要高。显然用“事后统计法”评估一个算法的时间开销，并不是一个好方法。这就要引入一个概念，时间复杂度。通过时间复杂度，我们就可以算法执行之前大致分析出一个算法在执行的时候的时间开销。

先来看一段代码，求1,2,3...n的累加和。

我们为了大致估算出这段代码的时空开销，可以假设每一行代码的执行时间都一样，记为T。那么第3，第4行就分别用了2个T，第5、7循环行执行了n次，需要n个T，第9行执行1次，需要的时间是T。那么就可以得出这段代码的总的执行时间是(2n+3)*T。可以看出来，所有代码执行的总时间T(n)与每行代码的执行次数成正比。

按照这个思路，再来看这段代码

我们依旧假设每个语句的执行时间是T。那么这次代码总的执行T(n)时间是多少呢？

第2、3、4行代码各自需要一个T，一共需要3T的时间，第5、6行分别需要执行nT,一共2nT，第6、7行分别循环执行了n²遍，一共需要2n²T。所以代码总的执行时间为(2n² +2n+3)T.

通过以上两段代码的分析，我们可以得到一个重要的规律：所有代码的执行时间T(n)与每一行代码的执行次数f(n)成正比。我们把这个规律总结成一个公式：

我来具体解释一下这个公式。其中，T(n) 我们已经讲过了，它表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

3)。大O时间复杂度实际上并不是具体的代码执行时间，而是表示代码执行时间随着数据规模的变化趋势，所以也叫做渐进式间复杂度，简称时间复杂度。当n非常大的时候，公式中的低阶、常量、系数并不能左右增长趋势，所以都可以忽略。我们只需要记住一个最大量级就好了，如果用大O表示法来表示刚刚说过的两段代码的时间复杂度，就可以记为T(n) = O(n); T(n) = O(n²);

关于时间复杂度的分析，这里有三个比较实用的方法。

1. 只关注循环次数比较多的一段代码
   我们前面说过，可以忽略掉公式中的低阶、系数和常量。所以，我们在分析一段代码的时间复杂度的时候，只需要关注循环执行次数最多的那一段代码即可。而这段代码核心执行次数的n的量级，就是整段代码的时间复杂度。
   

如果之关注循环次数最多的第4第5行代码，之前说过，这两行代码被执行了n次，所以时间复杂度就是O(n)。

1. 加法法则：总复杂度等于量级最大的那段代码的复杂度
   

这段代码一共分为三个部分，我们可以依次分别求出这三部分的时间复杂度，然后在放在一起比较，找到量级最大的作为整段代码的时间复杂度。

第一部分循环最多的代码执行了100次，是一个常量，跟n的规模无关。所以时间复杂度为O(1)。这里要强调的是，哪怕这里写的不是100，而是，这都是一个常量，时间复杂度都为O(1)。

第二部和第三部分的时间复杂度分别为O(q),和O(n²)。分析方法一样，这里就不在多说了。综合这三部分代码的时间复杂度，我们去最大的量级，最终得到的结果就是O(n²)。
我们也可以将这段代码抽象为一个公式：

1. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

把乘法法则总结成公式，就是这样的：

几种常见的时间复杂度实例分析。

对于以上罗列的量级，我们可以粗略的分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2ⁿ)和O(n!)。当数据规模越来越大的时候，非多项式算法的执行时间会急剧增加，求解问题的会无限增长。所以非多项式量级算法是非常低效的算法。我们主要来看几种常见的多项式时间复杂度：

首先必须要明确一个概念，O(1)只是常量级时间复杂度的一种表示方法，并不是只执行了一行代码。比如这一段代码，几遍有三行，它的时间复杂度也是O(1)，而不是O(3)。

一般情况下，算法中不存在循环语句，递归语句，即使有成千上万行代码，其时间复杂度也是O(1)。

对数阶的复杂度也非常常见，同时也是比较难分析的一种时间复杂度。

对于这个例子，我们只需要求出i = i * 2这一行执行了几次即可。这里的i每次都乘以2。也就是说i是一个指数增长的模型，即i = 2^x（x表示代码执行的次数）。根据循环结束的条件，i>n时，循环结束，用2^x = n，可以求出循环结束时代执行的次数x = 现在，把代码稍稍改动一下：

还是按照刚刚的分析思路，就可以知道时间复杂度是O(log₃n)。实际上，不管是O(log₂n)还是O(log₃n),我们都可以把所有的对数阶的时间复杂度都记为O(logn)。我们知道，对数之间是可以互相转换的，log₃n 就等于 log₃2 * O(log₃n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

在此基础之上O(nlogn)就很容易理解了。我们说过乘法法则，如果一段代码的时间复杂度是O(logn)，我们把它放在循环里面执行n遍，时间复杂度就是O(nlogn)了。

接下来再来说一个跟前面都不一样的时间复杂度，有两个数据的规模来决定。

从代码中可以看出，m和n是两个不同的数据规模。我们无法事先评估出n和m的量级谁大，所以我们在表示时间复杂度的时候，就不能简单的利用加法法则，省略其中的一个。所以上面代码的时间复杂度为O(m+n)。

在数组中查找一个数据，并不需要每次都把数组从头到尾都遍历一遍，而是在遍历到过程中，查找到就退出循环。

这时候，时间复杂度显然就不是O(n）了。因为变量x可能出现在数组中的任意一个位置。如果第一个元素恰好是x,那么就不需要在继续往后遍历了，那时间复杂度就是O(1)。如果数组中不存在x，那么我们就得把整个数组都遍历一遍，时间复杂度就变成了O(n)。所以，不同的情况，时间复杂度是不一样的。

为了表示代码在不同条件下时间复杂度，我们需要引入三个概念，最好情况时间复杂度，最坏情况时间复杂度和平均时间复杂度。

顾名思义，最好时间复杂度就是在最理想的情况下执行这段代码的时间复杂度。就是我们刚刚提到的，如果数组中第一个元素就是要查找的元素，这个时候对应的时间复杂度就是最好情况时间复杂度。同样的道理，最坏情况时间啊复杂度就是在最糟糕的情况下，执行这段代码的时间复杂度。就像刚刚的例子，如果整个数组中不存在变量x，这种情况下对应的时间复杂度就是最坏情况下时间复杂度。

最好、最坏情况时间复杂度都是一个极端情况下代码的复杂度，发生的可能性并不大。为了更好的表示时间复杂度，我们需要引入另一个概念，平均时间复杂度。还说刚刚查找x的例子。一共有n+1种情况：要查找的数据在数组的0~n-1的位置中，和不在数组中。我们把每种情况下需要遍历数组的次数累加起来，然后再除以n+1，就可以得到平均的查找次数了：

在时间复杂度的大O表示法中，可以省略掉系数，低阶和常量。所以，简化之后的平均复杂度是O(n)。至此，结论已经得出了，但是推导过程是有一些问题的。我们刚刚讲到的n+1种情况，出现的概率并不一样。

用大O表示法之后，去掉系数和常量，得到的平均复杂度也为O(n)。

均摊时间复杂度，听起来跟平均时间复杂度有点像。对于初学者来说，这两个概念确实非常容易弄混。前面说了，大部分情况下我们并不需要区分最好、最坏、平均三种复杂度。平均复杂度只是在某种特殊情况才会用到，而均摊时间复杂度的应用场景更加特殊、更加有限。来看一段代码：

 // array表示一个长度为n的数组
 

我先来解释一下这段代码。这段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。

在最理想的情况下，数组中有空余空间，我们只需要将数据插入到数组下标为count的位置就可以了，所以最好时间复杂度为O(1)。最坏情况下数组中没有空余空间了，我们需要做一下遍历求和，然后再将数据插入，所以最坏时间复杂度为O(n)。那平均时间复杂度呢？还可以从概率论的角度分析。

所以平均时间复杂度就是O(1)。

其实这里的平均时间复杂度分析并不需要这么复杂，不需要引入概率论的知识。我们先来对比一下insert()例子和find()例子。

首先，find()函数在极端情况下复杂度才为O(1)。但是insert()在大部分情况下时间复杂度都为O(1)，只有个别情况下复杂度才比较高，为O(n)。

其次，对于insert()函数O(1)时间复杂度和O(n)时间复杂度的出现是非常有规律的。而且具有一定的前后时序关系，一般都是一个O(n)之后跟着n-1个O(1)，循环往复。

所以针对这种特殊的场景，我们引入了一种更加简单的分析方法：摊还分析法，通过摊还分析法得到的一个时间复杂度叫均摊时间复杂度。我们还以这个insert()函数为例，大致思路就是：每一次O(n)插入操作，都会跟着n-1次的O(1)插入操作。所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上，均摊下来，这一组连续的操作就是O(1)。这既是均摊分析的大致思路。

尽管很多数据结构和算法书籍都花了很大力气来区分平均时间复杂度和均摊时间复杂度，但其实我个人认为，均摊时间复杂度就是一种特殊的平均时间复杂度，我们没必要花太多精力去区分它们。你最应该掌握的是它的分析方法，摊还分析。至于分析出来的结果是叫平均还是叫均摊，这只是个说法，并不重要。

总结来说，时间复杂度也称为渐进时间复杂度，可以分析算法执行的效率和问题规模n之间的增长关系。越是高阶的复杂度算法，执行效率越是低下。

与时间复杂度类似，空间复杂度描述的是内存空间开销与问题规模n之间的关系。先来看一段代码：

我们假设一个int类型数据占4个字节，这段代码一共定义了三个变量，分别是int n4字节、int flag[n]4n字节，int i4字节。那么该段代码一共需要4n+4+4=4n+8个字节的内存储存变量。我们只关心最高阶，不考虑系数、常量。所以这段代码的空间复杂度为S(n) = O(n)。前面说过在分析一个算法的时间复杂度的时候，不需要考虑与问题规模无关的行，类比这个思想，在来看一段代码：

这里我们只需要考虑第3、4行即可。这两行一分别需要向内存申请n*n个字节和n个字节的地址空间。我们区最高阶，所以空间复杂度S(n) = O(n²)。

函数递归调用地时候需要的内存开销

如果函数递归调用，那么情况就有些复杂了：

这是一个递归函数，首先定义了三个变量a,b,c。判断输入n的值，如果n>1会，会调用调用自身，但是传入的参数是n-1；如果n不小于1，则会输出“This is a function %d”。为了便于理解，我们假设传入n的初值为5，来具体分析一下。

这里我们并不关心输出结果，根据刚才的层层分析，我们注意到，程序一共从层调用了5层，定义了5次变量。如果层层调用n次，需要定义n次变量，所以空间复杂度就是O(n)。

至此，我们已经知道了,递归调用的层数与空间复杂度是有关的，所以在遇到这种递归算法的空间复杂度的时候，分析它调用的深度是非常有必要的。