数据结构与算法复习整理（一）——基本概念
数据结构+算法=程序
数据结构主要研究数据的组织、存储及运算方法。
数据结构与算法的研究设计构筑计算机求解问题过程的两个重要方面：刻画实际问题中信息及其关系的数据结构和描述问题解决方案的逻辑抽象算法。
数据结构的相关术语：
- 数据：描述客观事物的数值、字符以及能输入到计算机中且能被处理的各种符号集合。
- 数据元素：组成数据的基本单位，是数据集合的个体，计算机中通常作为一个整体进行考虑和处理。
- 数据对象：性质相同的数据元素的集合，是数据的一个子集。
- 数据结构：相互之间存在一种或多种特定关系的数据元素集合。数据元素相互之间的关系称为“结构”，即数据的组织形式，因此也说数据结构是带有结构的数据元素的集合。
- 数据类型：一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。
- 数据抽象与抽象数据类型。
数据结构的内容
包含三个方面的内容：数据的逻辑结构、数据的存储结构和数据的运算。
1.数据的逻辑结构
数据的逻辑结构是指数据元素之间逻辑关系的描述。
根据数据元素之间关系的不同特性，通常有以下四种结构：
- 集合结构：结构中的元素之间除了同属于一个集合的关系外，无任何其他关系。
- 线性结构：结构中的元素之间存在着一对一的线性关系。
- 树形结构：结构中的元素之间存在着一对多的层次关系。
- 图状结构：结构中的元素之间存在着多对多的任意关系。
根据元素之间关系的不同特性，数据结构又可分为线性结构和非线性结构。
其中线性结构有：线性表、栈、队列、字符串、数组和广义表；
非线性结构有树和图。
2.数据的存储结构
数据元素的关系在计算机中有两种表示方法：顺序映像和非顺序映像。即在计算机内不同的存储结构：顺序存储和链式存储。
顺序存储的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。（即在内存中的地址是连续的）
链式存储的特点是借助指针表示数据元素之间的逻辑关系。（在内存中的地址是随机的）
逻辑结构与存储结构的关系：存储结构是逻辑关系的映像与元素本身的映像，是数据结构的实现；逻辑结构是数据结构的抽象
任何一个算法的设计取决于选定的数据结构，算法的实现依赖于采用的存储结构。
综上，数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。
3.数据的运算（即算法）
算法的特性：有穷性，确定性，可行性，有输入和输出。（程序可以不满足算法的有穷性，比如操作系统，嵌入式开发等，都是在一个无限循环中执行的程序）
算法的评价标准：
- 正确性
- 可读性
- 健壮性（鲁棒性）
- 高效率与低存储量需求
（其中正确性一般可分为四个层次：（1）程序不含语法错误；（2）程序对几组输入数据能够得出满足规格说明要求的结果；（3）程序对于精心选择的典型、苛刻而带有刁难性的机组输入数据能够得出满足规格说明要求的结果；（4）程序对于一切合法输入数据都能够产生满足规格说明要求的结果）
算法的性能分析
算法的性能分析有两个层面：时间与空间
（1）时间复杂度
分析算法时，存在几种可能的考虑：
算法完成工作最少需要多少基本操作，即最优时间复杂度
算法完成工作最多需要多少基本操作，即最坏时间复杂度
算法完成工作平均需要多少基本操作，即平均时间复杂度
对于最优时间复杂度，其价值不大，因为它没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值。
对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的实例分布可能并不均匀而难以计算。
对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作。
因此，我们主要关注算法的最坏情况，亦即最坏时间复杂度。
时间复杂度的几条基本计算规则：
- 基本操作，即只有常数项，认为其时间复杂度为O(1)
- 顺序结构，时间复杂度按加法进行计算
- 循环结构，时间复杂度按乘法进行计算
- 分支结构，时间复杂度取最大值
- 判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略
- 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度
常见时间复杂度
所消耗的时间从小到大
O(1) < O(log n) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
（2）空间复杂度
指的是算法在计算机内执行时所需存储空间的度量。记作：S(n)=O(f(n))
算法执行期间所需要的存储空间包括3个部分：
（1）算法程序所占的空间。
（2）输入初始数据所占的存储空间。
（3）算法执行过程中所需要的额外空间。
常用的排序算法的时空复杂度：