1 绪论

2018-01-01 本文已影响0人 coderjiege

1.1 什么是数据结构（Data Structure）

数据结构是对现实世界中数据及其关系的某种映射，既可以表示数据本身的物理结构，也可以表示计算机中的逻辑结构。

1.1.1 数据的逻辑结构（Logical Structure）

数据的逻辑结构由数据结点（Node）和连接两个结点的边（Edge）组成

结点的数据类型：

整型（integer）：1-4个字节
实数（real）：4-8个字节
布尔（boolean）
字符（char）：ASCII字符集中的字符，不包含汉子符号
指针（pointer）：指向某一内存单元的地址

结点的分类

线性结构（Linear Structure）：每个结点最多只有一个前驱结点和一个后继结点
树形结构（Tree Structure）：每个结点均有且只有唯一的前驱结点，但可以有多个后继结点
图结构（Graph Structure）：每个结点的前驱结点数和后继结点数不做任何约束

线性结构和树形结构的区别：每个结点是否具有一个直接后继；树形结构和图结构的区别：每个结点是否仅仅从属于一个直接前驱

1.1.2 数据的存储结构

数据的存储结构就是建立一种逻辑结构到物理结构的映射。4种常用存储映射的方法：

顺序：紧凑存储结构
链接
索引
散列：散列函数（Hash Function）关键：如何选择和设计恰当的散列函数、构造散列表、研究构造散列表的碰撞解决方案

1.2 算法与算法设计

1.2.1 算法的概念

算法（Algorithm）是为解决某一特定问题而采取的具体而有限的操作步骤。程序是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解。算法性质：

通用性
有效性
确定性
有穷性

1.2.2 算法设计

穷举法（也称为枚举法）（Enumeration）：需要有明确的穷举范围和穷举规则，浪费时间，效率低。
回溯法（Backtrack）（也称为试探法）：放弃当前候选解，寻找下一个候选解的过程叫做回溯。扩大当前候选解的范围，以继续试探的过程称为向前试探。
分治法（Divide and Conquer）和递归法（Recursion）：大问题分割成小问题，以便各个击破，分而治之，然后把各个子问题的解合并起来，得出整个问题的解。分治法是一种自顶向下的设计方法。反复利用分治手段，使问题规模不断缩小，最终缩小到容易直接求解的规模，这自然会导致递归过程的产生。分治法和递归法如同一对孪生兄弟，经常同时应用在算法设计中，并由此产生很多高校算法。
贪心法（Greedy）和动态规划法（Dynamic Programming）：贪心法所做出的选择只是在某种意义上的局部最优解，寄希望于由局部最优解构建全局最优解。DP也是求解某种最优性质的问题。

1.3 算法分析

1.3.1 算法的渐进分析

o（1）、o（n）、o（nlogn）、o（n^2）、o（a ^ n）（指数增长）：在n很大的时候其大小差别非常大。
具有指数增长率的算法简称指数爆炸型算法，在应用时需要谨慎使用。
循环中嵌套循环会增加算法的复杂度，但也并非总是如此。

for (i = 4; i < n; i++) 
for (j = i - 3; sum = a[i - 4]; j <= i; j++)
    sum += a[i];

此时，外层循环n-4次，对每个i而言，内层循环只执行4次，每次的操作次数与i的大小无关，尽管存在循环嵌套，但算法的整体时间复杂度依然呈线性增长。

1.3.2 最坏、最好和平均情况

最好情况：帮助了解某个算法在何种情况下使用好。
最坏情况：帮助了解某个算法至少能做多快，这点在实时系统中尤其重要。因为在一些重要的场景下不能在规定时间内解决问题的算法的是不可接受的。

1.3.3 时间和空间资源开销

对于静态数据结构（一旦输入数据和问题规模确定下来，它的数据结构大小也就确定下来）：一般将仅限于讨论时间开销。
在算法运行过程中，数据结构所占用的空间有时会有数量级的增大或缩小，对于这种情况，空间开销的分析和估计是十分必要的。

时间资源的折中原理：时空折中。指为了改善一个算法的时间开销，往往可以通过增大空间开销为代价。如：用散列函数，将问题时间复杂度由线性增长改善为常数时间，而空间开销方面则增添了一个线性增长的存储空间。在设计算法时，经常采用这种空间换时间的办法。当然也有牺牲计算机运行时间，通过增大时间开销来换取存储空间的节省的时间换空间的算法，如树的顺序存储。