数据结构浅析（二）：算法
一、前言
我们常常会看到《数据结构与算法》之类的书，那么数据结构和算法为什么会在一起呢？通过上一篇 数据结构基本概念 我们知道，数据结构是互相之间存在一种或多种特定关系的数据元素的集合。这里的 一种或多种特定关系的处理就涉及到算法，所以对于完整的程序设计 数据结构 和 算法 都很重要。
本篇主要介绍算法的一些概念内容，方便后面的数据结构学习。
二、什么是算法？
算法（Algorithm） 英文词最早是由 9 世纪 波斯数学家花拉子米 提出，欧几里得算法被人们认为是史上第一个算法。如今普遍对算法的定义是：算法是决定特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
简而言之也就是为了解决某个或某类问题，需要把指令表示成一定的操作序列，操作序列包括一组操作，每一个操作都完成特定的功能，这就是算法了。
三、算法的特征
算法具有五个基本特征：输入、输出、有穷性、确定性、可行性
前面三个从字面很容易理解，简单说下后面两个；
确定性 指算法在一定确定条件下，相同的输入只可能有唯一的输出结果；
可行性 指算法的每一步都可以通过执行有限次数完成。
四、算法设计的要求
好算法的基本要求有：正确性、可读性、健壮性、时间效率高和存储量低
4.1、正确性
算法的正确性指算法至少具有输入、输出、加工处理无歧义、能正确反映问题需求、能得倒问题的正确答案。
具体到程序大体分为下面 4 个层次：
- 算法程序没有语法错误；
- 算法程序对于合法的输入数据能够产生满足要求的输出结果；
- 算法程序对于非法的输入数据能够得出满足规格说明的结果；
- 算法程序对于极端的测试数据都有满足要求的输出结果。
证明一个复杂算法正确性代价很高，很难通过程序证明，一般采用数学方法证明，满足前 3 个层次就可以说是一个合格的算法了。
4.2、可读性
程序设计很多时候不是一个人搞定的，便于阅读理解还是很重要的。
4.3、健壮性
当输入数据不合法时，算法能做出相关处理，而不是产生异常或莫名其妙的结果，那么这就是健壮的算法。
4.4、时间效率高和存储量低
时间效率高是相对的。对于同一个问题，如果有多个算法可以解决，执行时间短的就是效率高的；
存储量指的是算法在执行过程中需要的最大内存和外部硬盘存储空间。我们生活中中希望花最少的钞票、最少的时间办最大的事，算法也是如此。
五、算法时间复杂度
5.1、什么是算法时间复杂度？
算法时间复杂度，是算法的时间量度，记作：T ( n ) = O ( f ( n ) )
n 表示问题规模；T ( n ) 表示语句总的执行次数；f ( n ) 是问题规模 n 的某个函数；大 O ( ) 用来记录算法时间复杂度，如我们常见的 O ( 1 )、O ( n ) 、O ( n^2 ) ....
一般情况下，随着 n 的增大， T ( n ) 增长最慢的算法为最优算法。
5.2、怎么分析出算法的时间复杂度？
如何分析出一个算法的时间复杂度呢？这里有个分析时间复杂度的推导方法：
- 用常数 1 取代运行时间中的所有加法常数；
- 在修改后的运行次数函数中，只保留最高阶项；
- 如最高阶项存在且不是 1 ，则去除与这个项相乘的常数。
下面分析一些简单的算法时间复杂度。
5.3、常数阶
例如：求 1+2+3+...+100 和
我们很容易想到的是 高斯算法，如下：
int sum = 0, n = 100; /* 执行一次 */
sum = (1 + n) * n / 2; /* 执行一次 */
printf("%d", sum); /* 执行一次 */
由 T ( n ) = O ( f ( n ) )，找到依次数据，很容易得到 f ( n ) = 3；根据上面给出的推到方法，我们很容易得出 高斯算法 的时间复杂度为O (1)
5.4、线性阶
举个例子，如下：
for (i = 0; i < n; i++ )
{
/* 时间复杂度为 O (1) 的程序步骤序列 */
}
循环体中的代码需要执行 n 次，即 f( n ) = n，所以它的时间复杂度为 O( n )
5.5、对数阶
举例如下：
int count = 1;
while (count < n)
{
count = count * 2;
}
每次 count * 2 之后，就距离 n 更近一分。那么有多少个 2 相乘后大于 n 退出循环？ 数学表示来看也就是 2^x = n ，得到 x = log(2 为底 n 的对数） [markdown 写数学公式功底不够，理解就好...]，得出 T( n ) = logn;
5.6、平方阶
下面是一个循环嵌套例子：
int i, j;
for (i = 0; i< n; i ++)
{
for (j = 0; j < n; j++)
{
/* 时间复杂度为 O(1) 的程序步骤序列 */
}
}
外层和内层的时间复杂度都是 O(n)，所以这段代码的时间复杂度是 O(n^2).
再看下面一个循环嵌套例子：
int i, j;
for (i = 0; i< m; i ++)
{
for (j = 0; j < n; j++)
{
/* 时间复杂度为 O(1) 的程序步骤序列 */
}
}
外层和内层的时间复杂度依次为 O(m), O(n)，所以这段代码的时间复杂度是 O(m * n)
接着再看一个例子：
int i, j;
for (i = 0; i < n; i++)
{
for (j = i; j < n; j++)
{
/* 时间复杂度为 O(1) 的程序步骤序列*/
}
}
当 i = 0 时，内循环执行 n 次；当 i = 1 时，内循环执行 n-1 次；......；当 i = n -1时，执行 1 次。所以总的执行次数为：
n + (n - 1) + (n - 2) + ... + 1 = n(n + 1) / 2 = n^2 / 2 + n / 2
根据前面的推导方法，很容易得到这段代码的时间复杂度为 O(n^2).
5.7、常见时间复杂度
常见时间复杂度如表：
| 执行次数 | 函数阶 | 非正式术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n + 3 | O(n) | 线性阶 |
| 3n^2 + 2n + 1 | O(n^2) | 平方阶 |
| 6n^3 + 2n^2 + 3n +4 | O(n^3) | 立方阶 |
| 5log2n + 20 | O(logn) | 对数阶 |
| 2n + 3nlog2n + 19 | O(nlogn) | nlogn 阶 |
| 2^n | O(2^n) | 指数阶 |
常用时间复杂度所消耗时间从小到大依次为：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
# 其中的 指数阶 和 阶乘阶 很少用到，你懂的...
六、算法空间复杂度
算法的空间复杂度通过计算算法所需的存储空间实现，计算公式： S(n) = O( f( n ) )，n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数。
通常，我们使用时间复杂度来指运行时间的需求，用空间复杂度指空间需求。
七、总结
本篇提到的算法时间复杂度用处还是挺多的，后面自己写程序过程中也尽可能得降低时间复杂度。
本篇参考：
戳这里 前往我的小屋：I'm Jony
