基本

• 《数据结构（C语言版）》严蔚敏、吴伟民 编著 清华大学出版社 2017
• 《算法设计技巧与分析》[沙特] M.H.Alsuwaiyel 著 吴伟昶 方世昌 等译 电子工业出版社 2016

1 基本概念和术语

• **数据（data）**是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
• **数据元素（data element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。有时，一个数据元素可由若干个数据项（data item）**组成
• **数据对象（data object）**是性质相同的数据元素的集合，是数据的一个子集。
• **数据结构（data structure）**是相互之间存在一种或多种特定关系的数据元素的集合。
• 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（structure）。
• 根据数据元素之间关系的不同特性，通常有下列4类基本结构：
  • 集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系；
  • 线性结构：结构中的数据元素之间存在一个对一个的关系；
  • 树形结构：结构中的数据元素之间存在一个对多个的关系；
  • 图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。
• 数据结构的形式定义：数据结构是一个二元组Data Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。
• 数据结构包括“逻辑结构” 和“物理结构”两个方面(层次)
  • 结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。
  • 数据结构在计算机中的表示（又称映像）称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。
  • 任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。
• 数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。
  • 顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
  • 非顺序映像的特点是借助指示元素存储地址的指针（pointer）表示数据元素之间的逻辑关系
• (拓展)关系的映象方法：
  • 顺序映象（顺序存储方法）：以相对的存储位置表示后继关系
  • 链式映象（链接存储方法）：以附加信息(指针)表示后继关系
  • 索引存储方法：通过建立存储结点信息，以及建立附加的索引表来标识结点的地址的存储方法。
  • 散列存储方法：由节点的关键码值决定节点的存储地址。
• **数据类型(data type)**是一个值的集合和定义在这个值集上的一组操作的总称。
• 按“值”的不同特性，高级程序语言中的数据类型可分为两类：
  • 非结构的原子类型：原子类型的值是不可分解的，例如C语言中的基本类型（整型、实型、字符型和枚举类型）、指针类型和空类型。
  • 结构类型：结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。例如数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。在某种意义上，数据结构可以看成是“一组具有相同结构的值”，则结构类型可以看成由一种数据结构和定义在其上的一组操作组成。
• **抽象数据类型（Abstract Data Type，简称ADT）**是指一个数学模型以及定义在该模型上的一组操作。
  • 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。（支持了逻辑设计和物理实现的分离，支持封装和信息隐蔽）
  • 抽象数据类型和数据类型实质上是一个概念。例如，各个计算机都拥有的“整数”类型是一个抽象数据类型，尽管它们在不同处理器上实现的方法可以不同，但由于其定义的数学特性相同，在用户看来都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。
• 若按其值的不同特性，抽象数据类型可细分为下列3种类型：
  • **原子类型（atomic data type）**属原子类型的变量的值是不可分解的。这类抽象数据类型较少，因为一般情况下，已有的固有数据类型足以满足需求。但有时也有必要定义新的原子数据类型，例如数位为100的整数。
  • **固定聚合类型（fixed-aggregate data type）**属该类型的变量，其值由确定数目的成分按某种结构组成。例如，复数是由两个实数依确定的次序关系构成。
  • **可变聚合类型（variable-aggregate data type）**和固定聚合类型相比较，构成可变聚合类型“值”的成分的数目不确定。例如，可定义一个“有序整数序列”的抽象数据类型，其中序列的长度是可变的。
  • 显然，后两种类型可统称为结构类型。
• 抽象数据类型的形式定义：三元组表示(D，S，P)其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。

2 算法分析

• **算法（algorithm）**是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

• 算法具有5个重要特性：

  • 有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
  • 确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得出相同的输出。
  • 可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
  • 输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
  • 输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。

• 算法设计的要求：

  • 正确性（correctness）：算法应当满足具体问题的需求。

    “正确”一词的含义在通常的用法中有很大差别，大体可分为以下4个层次：a.程序不含语法错误；b.程序对于几组输入数据能够得出满足规格说明要求的结果；c.程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；d.程序对于一切合法的输入数据都能产生满足规格说明要求的结果。显然，达到第d层意义下的正确是极为困难的，所有不同输入数据的数量大得惊人，逐一验证的方法是不现实的。对于大型软件需要进行专业测试，而一般情况下，通常以第c层意义的正确性作为衡量一个程序是否合格的标准。

  • 可读性（readability）：算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。

  • 健壮性（robustness）：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明其妙的输出结果。

  • 效率与低存储量需求：通俗地说，效率指的是算法执行的时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。效率与低存储量需求这两者都与问题的规模有关。求100个人的平均分与求1000个人的平均分所花的执行时间或运行空间显然有一定的差别。

• 算法的效率包括时间代价（时间复杂性）和空间代价（空间复杂性），两者都与问题的规模有关。

• 一般情况下，算法中基本操作重复执行的次数是问题规模$n$的某个函数$f(n)$，算法的时间量度记作$T(n)=O(f(n))$，它表示随问题规模$n$的增大，算法执行时间的增长率和$f(n)$的增长率相同，称做算法的渐近时间复杂度（asymptotic time complexity），简称时间复杂度。（算法中关键操作重复执行的次数是规模$n$的某个函数$T(n)$​）

  • 换言之：当且仅当存在正整数$c$和$n_0$ ，使得$T(n)<= c*f(n)$对所有的$n>= n_0$成立，则称该算法的时间增长率在$O(f(n))$中，记为$T(n) = O(f(n))$​。

• 类似于算法的时间复杂度，以**空间复杂度（space complexity）**作为算法所需存储空间的量度，记作$S(n)=O(f(n))$​，其中n为问题的规模（或大小）。

  • 一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。
  • 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间，否则应同时考虑输入本身所需空间（和输入数据的表示形式有关）。
  • 若额外空间相对于输入数据量来说是常数，则称此算法为原地工作；又如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。

• O符号（上界）：

  • 一般地，说一个算法的运行时间是$O(g(n))$，是指如果每当输入的大小等于或超过某个阀值$n_0$时，那么它的运行时间上限是$g(n)$的c倍，其中c是某个正常数。该符号的形式定义如下：

    令 $f(n)$ 和 $g(n)$ 是从自然数集到非负实数集的两个函数, 如果存在一个自然 数 $n_{0}$ 和一个常数 $c>0$​, 使得

    $\forall n \geqslant n_{0}, f(n) \leqslant c g(n)$

    则称 $f(n)$ 为 $O(g(n))$ 。
    因此, 如果 $\lim _{n \rightarrow \infty} f(n) / g(n)$ 存在, 那么$\lim _{n \rightarrow \infty} \frac{f(n)}{g(n)} \neq \infty$ 蕴含着 $f(n)=O(g(n))$

  • 非形式地，这个定义说明$f$没有$g$的某个常数倍增长得快。

  • $O(1) <O(log_2n) < O(n) < O(nlog_2n) < O(n^2) < O(n^3) <O(2^n ) < O(3^n) < O(n!)$​

• $\Omega$​ 符号（下界）：

  • 一般而言，如果输人大小等于或大于某一阈值 $n_{0}$, 它的运行时间下界是 $g(n)$ 的 $c$ 倍, $c$ 是某个正常数, 则称算法是 $\Omega(g(n))$ 。该符号的形式定义如下：

    令 $f(n)$ 和 $g(n)$ 是从自然数集到非负实数集的两个函数, 如果存在一个自然 数 $n_{0}$ 和一个常数 $c>0$​, 使得

    $\forall n \geqslant n_{0}, f(n) \geqslant c g(n)$

    则称 $f(n)$ 为 $\Omega(g(n))$ 。
    因此, 如果 $\lim _{n \rightarrow \infty} f(n) / g(n)$ 存在, 那么$\lim _{n \rightarrow \infty} \frac{f(n)}{g(n)} \neq 0$ 蕴含着 $f(n)=\Omega(g(n))$

  • 非正式地, 这个定义说明 $f$ 的增长至少和 $g$ 的某个常数倍一样快。

  • $f(n)$​ 是 $\Omega(g(n))$​，当且仅当 $g(n)$​ 是 $O(f(n))$​

• $\Theta$​ 符号 ​​（精确阶）：

  • 一般来说，对于任何大小等于或超过某一阈值 $n_{0}$ 的输人，如果运行时间在下限 $c_{1} g(n)$ 和上限 $c_{2} g(n)$ 之间 $\left(0<c_{1} \leqslant c_{2}\right)$, 则称算法的运行时间是 $\Theta(g(n))$ 阶的。因此, 这一符号是用来表示算法的精确阶的, 它蕴含着在算法的运行时间上有确切界限。该符号的形式定义如下：

    设 $f(n)$ 和 $g(n)$ 是从自然数集到非负实数集的两个函数, 如果存在一个自然 数 $n_{0}$ 和两个正常数 $c_{1}$ 和 $c_{2}$​​​​, 使得

    $\forall n \geqslant n_{0}, c_{1} g(n) \leqslant f(n) \leqslant c_{2} g(n)$

    则称 $f(n)$ 是 $\Theta(g(n))$ 的。
    因此, 如果 $\lim _{n \rightarrow \infty} f(n) / g(n)$ 存在, 那么

    \lim _{n \rightarrow \infty} \frac{f(n)}{g(n)}=c \text { 蕴含 } f(n)=\Theta(g(n))

    其中 $c$ 必须是一个大于 0 的常数。

  • 重要推论：$f(n)=\Theta(g(n))$, 当且仅当 $f(n)=O(g(n))$ 并且 $f(n)=\Omega(g(n))$

  • 可以认为 $O$​ 类似于$\leqslant$​, $\Omega$​ 类似于$\geqslant$, 而 $\Theta$ 类似于 $=$

• $o$​​符号：

  • 复杂性类

  • 定义如下：

    令 $f(n)$ 和 $g(n)$ 是从自然数集到非负实数集的两个函数, 如果对每一个常数 $c>0$, 存在一个正整数 $n_{0}$, 使得对于所有的 $n \geqslant n_{0}$, 都有 $f(n)<c g(n)$ 成立, 则称 $f(n)$ 是 $o(g(n))$ 的。因此, 如果 $\lim _{n \rightarrow \infty} f(n) / g(n)$ 存在, 那么

    \lim _{n \rightarrow \infty} \frac{f(n)}{g(n)}=0 \text { 蕴含着 } f(n)=o(g(n))

  • 非形式地, 这个定义是说, 当 $n$ 趋于无穷时, $f(n)$ 对于 $g(n)$ 可以忽略不计

  • $f(n)=o(g(n))$, 当且仅当 $f(n)=O(g(n))$, 但 $g(n) \neq O(f(n))$​

  • $1<\log \log n<\log n<\sqrt{n}<n^{3 / 4}<n<n \log n<n^{2}<2^{n}<n !<2^{n^{2}}$

• 平摊分析：在平摊分析中，可以算出算法在整个执行过程中所用时间的平均值，称为该运算的平摊运行时间。平摊分析保证了运算的平均代价，进而也保证了算法在最坏情况下的平均开销。这与平均时间分析不同，在平均分析中，要计算同样大小的所有实例才能得到平均值，它也不像平均情况分析，不需要假设输入的概率分布。（每个元素插入1次，每个元素至多删除1次）

3 编程

• 枚举
• 模拟

4 题目列表

试题链接	解题链接	备注