＜一＞数据结构（C++语言版）－绪论

2020-01-09 本文已影响0人爱学习的Whitley

１．计算机与算法

１．排序

将n个整数按通常的大小次序排成一个非降序列。这类操作统称排序（sorting）．

从前向后依次检查每一对相邻元素，一旦发现逆序即交换二者的位置。对于长度为n的序列，共需做n - 1次比较和不超过n - 1次交换，这一过程称作一趟扫描交换。需要反复进行多次扫描交换，直到序列中不再含有任何逆序的相邻元素。排序过程中，所有元素朝各自最终位置亦步亦趋的移动过程，犹如气泡在水中的上下沉浮，起泡排序（bubblesort）算法也因此得名。

图１起泡排序（bubblesort）算法

２．算法

什么是算法呢？所谓算法，是指基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列。算法应必须具备以下要素：

输入与输出

基本操作、确定性与可行性

有穷性与正确性

：证明算法有穷性和正确性的一个重要技巧，就是从适当的角度审视整个计算过程，并找出其所具有的某种不变性和单调性。其中的单调性通常是指，问题的有效规模会随着算法的推进不断递减。不变性则不仅应在算法初始状态下自然满足，而且应与最终的正确性相呼应－－当问题的有效规模缩减到0时，不变性应随即等价于正确性。

起泡排序算法的不变性和单调性可分别概括为：经过k趟扫描交换之后，最大的前k个元素必然就位；经过k趟扫描交换之后，待求解问题的有效规模将缩减至n - k。

3．要求

同一问题往往不限于一种算法，而同一算法也常常会有多种实现方式，因此除了以上必须具备的基本属性，在应用环境中还需从实用的角度对不同算法及其不同版本做更为细致考量和取舍。如：

退化与鲁棒性

退化（degeneracy）情况：除一般性情况外，实用的算法还应能够处理各种极端的输入实例。

鲁棒性（robustness）：就是要求能够尽可能充分地应对此类情况。

重用性

另一标准是：算法的总体框架能否便捷地推广至其它场合。实际上，起泡算法的正确性与所处理序列中元素的类型关系不大，无论是对于float、 char或其它类型，只要元素之间可以比较大小，算法的整体框架就依然可以沿用。算法模式可推广并适用于不同类型基本元素的这种特性，即是重用性的一种典型形式。

４．算法效率

包括：可计算性（computability），难解性（intractability），计算效率：从时间和空间等方面度量算法的计算成本，数据结构：要做到根据实际应用需求自如地设计、实现和选用适当的数据结构，必须首先对算法设计的技巧以及相应数据结构的特性了然于心，这些也是本书的重点与难点。

２．复杂度度量

１．时间复杂度

随着输入规模的扩大，算法的执行时间将如何增长？执行时间的这一变化趋势可表示为输入规模的一个函数，称作该算法的时间复杂度（ time　complexity）。具体地，特定算法处理规模为n的问题所需的时间可记作T(n)。从保守估计的角度出发，在规模为n的所有输入中选择执行时间最长者作为T(n)，并以T(n)度量该算法的时间复杂度。

小规模问题所需的处理时间本来就相对更少，故此时不同算法的实际效率差异并不明显；而在处理更大规模的问题时，效率的些许差异都将对实际执行效果产生巨大的影响。着眼长远、更为注重时间复杂度的总体变化趋势和增长速度的策略与方法，即所谓的渐进分析（ asymptotic analysis）．

１．大O记号（worst case）

图２　Ｔ(n)上界　大O记号

环境差异：

事实上，即便是同一算法、同一输入，在不同的硬件平台上、不同的操作系统中甚至不同的时间，所需要的计算时间都不尽相同。因此，有必要按照超脱于具体硬件平台和软件环境的某一客观标准，来度量算法的时间复杂度，并进而评价不同算法的效率差异。

基本操作－不妨将T(n)定义为算法所执行基本操作的总次数。

一种自然且可行的解决办法是，将时间复杂度理解为算法中各条指令的执行时间之和。在图灵机（Turing Machine, TM）和随机存储机（Random Access Machine, RAM）等计算模型中，指令语句均可分解为若干次基本操作，比如算术运算、比较、分支、子程序调用与返回等；而在大多数实际的计算环境中，每一次这类基本操作都可在常数时间内完成。

也就是说， T(n)决定于组成算法的所有语句各自的执行次数，以及其中所含基本操作的数目。

例子：起泡排序问题中，在每一轮内循环中，需要扫描和比较n - 1对元素，至多需要交换n - 1对元素。元素的比较和交换，都属于基本操作，故每一轮内循环至多需要执行2(n - 1)次基本操作。外循环至多执行n - 1轮。因此，总共需要执行的基本操作不会超过2(n - 1)＾2次。