一、什么是算法

算法，对应的英文单词是algorithm，这是一个很古老的概念，最早来自数学领域。

我们都听过高斯小时的故事和高斯算法，这里就不多说了，这是数学领域中算法的一个简单示例。在数学领域里，算法是用于解决某一类问题的公式和思想。

而我这里所讲的算法，是计算机科学领域的算法，它的本质是一系列程序指令，用于解决特定的运算和逻辑问题。从宏观上来看，数学领域的算法和计算机领域的算法有很多相通之处。

算法有简单的，也有复杂的。

简单的算法，诸如给出一组整数，找出其中最大的数。

复杂的算法，诸如在多种物品里选择装入背包的物品，使背包里的物品总价值最大，或找出从一个城市到另一个城市的最短路线。

算法有高效的，也有拙劣的。

比如高斯的故事中，高斯所用的算法显然是更加高效的算法，它利用等差数列的规律，四两拨千斤，省时省力地求出了最终结果。

而老师心中所想的算法，按部就班地一个数一个数进行累加，则是一种低效、笨拙的算法。虽然这种算法也能得到最终结果，但是其计算过程要低效得多。

在计算机领域，我们同样会遇到各种高效和拙劣的算法。衡量算法好坏的重要标准有两个。

• 时间复杂度
• 空间复杂度

算法的应用领域多种多样

• 运算
• 查找
• 排序

排序算法是实现诸多复杂程序的基石。

• 最优决策

有些算法可以帮助我们找到最优的决策。

• 面试

凡是已走上工作岗位的程序员，在面试过程中多多少少都经历过算法问题的考查，算法也是大多人的弱项和头疼的地方。

为什么面试官那么喜欢考查算法呢?

考查算法问题，一方面可以检验程序员对计算机底层知识的了解，另一方面也可以衡量一下程序员的逻辑思维能力。

二、什么是数据结构

数据结构，对应的英文单词是data structure，是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。

1. 线性结构

线性结构是最简单的数据结构，包括数组、链表，以及由它们衍生出来的栈、队列、哈希表。

2.树

树是相对复杂的数据结构，其中比较有代表性的是二叉树，由它又衍生出了二叉堆之类的数据结构。

3.图

图是更为复杂的数据结构，因为在图中会呈现出多对多的关联关系。

4.其他数据结构

除上述所列的几种基本数据结构以外，还有一些其他的千奇百怪的数据结构。它们由基本数据结构变形而来，用于解决某些特定问题，如跳表、哈希链表、位图等。

三、时间复杂度

为了解决时间分析的难题，引入了渐进时间复杂度(asymptotic time complexity)的概念，其官方定义如下：

若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))，O为算法的渐进时间复杂度，简称为时间复杂度。

因为渐进时间复杂度用大写O来表示，所以也被称为大O表示法。

其实就是时间复杂度就是把程序的相对执行时间函数，T(n)简化为一个数量级，这个数量级可以是n、n2、n3等。

如何推导出时间复杂度呢?有如下几个原则。

• 如果运行时间是常数量级，则用常数1表示

• 只保留时间函数中的最高阶项

• 如果最高阶项存在，则省去最高阶项前面的系数

场景1

T(n) = 3n，

最高阶项为3n，省去系数3，则转化的时间复杂度为:T(n)=O(n)。

场景2

T(n) = 5logn，

最高阶项为5logn，省去系数5，则转化的时间复杂度为:T(n) =O(logn)。

场景3

T(n) = 2，

只有常数量级，则转化的时间复杂度为:T(n) =O(1)。

场景4

T(n) = 0.5n2+ 0.5n，

最高阶项为0.5n2，省去系数0.5，则转化的时间复杂度为:T(n) =O(n2)。

四、空间复杂度

在时间复杂度相同的情况下，算法占用的内存空间自然是越小越好。如何描述一个算法占用的内存空间的大小呢?这就用到了算法的另一个重要指标——空间复杂度(space complexity)。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它同样使用了大O表示法。

程序占用空间大小的计算公式记作S(n)=O(f(n))，其中n为问题的规模，f(n)为算法所占存储空间的函数。

1. 常量空间

当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作O(1)。比如下面程序

void fun1(int n){  int var = 3;  ...}

2. 线性空间

当算法分配的空间是一个线性的集合(如数组)，并且集合大小和输入规模n成正比时，空间复杂度记作O(n)。比如：

void fun2(int n){  int[] array = new int[n];   ...}

3. 二维空间

当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n成正比时，空间复杂度记作O(n2)。

void fun3(int n){  int[][] matrix = new int[n][n];   ...}

4. 递归空间

递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合， 但是计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。

“方法调用栈”包括进栈和出栈两个行为。 当进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中。

当方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出。

下面这段程序是一个标准的递归程序:

void fun4(int n){   if(n<=1){    return;   }  fun4(n-1);   ...}

执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深 度是n，那么空间复杂度就是O(n)。

五、时间与空间的取舍

人们之所以花大力气去评估算法的时间复杂度和空间复杂度，其根本原因是计算机的运算速度和空间资源是有限的。

对于计算机系统来说也是如此。虽然目前计算机的CPU处理速度不断飙升，内存和硬盘空间也越来越大，但是面对庞大而复杂的数据和业务，我们仍然要精打细算，选择最有效的利用方式。

但是，正所谓鱼和熊掌不可兼得。很多时候，我们不得不在时间复杂度和空间复杂度之间进行取舍。

在绝大多数时候，时间复杂度更为重要一些，我们宁可多分配一些内存空间， 也要提升程序的执行速度。

六、小结

• 什么是算法

在计算机领域里，算法是一系列程序指令，用于处理特定的运算和逻辑问题。

• 衡量算法优劣的主要标准是时间复杂度和空间复杂度。

• 什么是数据结构

数据结构是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修 改数据。

数据结构包含数组、链表这样的线性数据结构，也包含树、图这样的复杂数据 结构。

• 什么是时间复杂度

时间复杂度是对一个算法运行时间长短的量度，用大O表示，记作T(n)=O(f(n))。

常见的时间复杂度按照从低到高的顺序，包括O(1)、O(logn)、O(n)、 O(nlogn)、O(n2)等。

• 什么是空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，用大O表示，记作S(n)=O(f(n))。

常见的空间复杂度按照从低到高的顺序，包括O(1)、O(n)、O(n2)等。其中递归算法的空间复杂度和递归深度成正比。