01.绪论

1. 概念

1.1 数据结构

• 数据 Data：信息的载体。能被计算机识别并处理的符号的集合。
• 数据元素 Data element：数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素往往由若干数据项组成。数据项是组成数据元素的不可分割的最小单位。

如学生的信息记录就是一个数据元素，它由学号、姓名、性别等组成。

• 数据对象 Data object：具有相同性质的数据元素的集合，是数据的一个子集。

• 数据类型 Data type：一个值的集合和定义在此集合上的一组操作的总称。

  • 抽象数据类型ADT( Abstract Data Type )：一个数学模型（逻辑结构）及在其上定义的一组操作。

• 数据结构 Data structure：相互之间存在一种或多种特定关系的数据元素的集合。数据结构包含三方面内容：逻辑结构、存储结构、数据的运算。

  • 逻辑结构： 数据结构的逻辑抽象、数据元素之间的数学关系.
  • 存储结构： 又称存储映像或结点，数据结构在计算机中的表示，也称物理结构.
    ::: tip 结点与节点
    结点：数据结构的物理存储结构.
    节点：在计算机网络中通常指拥有数据存储、转发能力的计算机设备终端.
    在数据结构中两者可以通用，但前者常用.
    :::

---

1.2 算法

1. 定义

算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。
算法组成要素：操作、控制结构、数据结构

• 操作：
  • 算术运算：加、减、乘、除。
  • 关系比较：大于、小于、等于、不等于。
  • 逻辑运算：与、或、非。
  • 数据传输：输入、输出、赋值（计算）。
• 算法的控制结构：
  算法的控制结构给出了算法的框架，决定了各操作的执行顺序。
  • 顺序结构：个操作依次进行。
  • 选择结构：有条件是否成立来决定选择执行。
  • 循环结构：有些操作要重复执行，直到满足某个条件才结束，这种控制结构也称为重复或迭代结构。
• 数据结构：
  算法操作的对象是数据，数据的逻辑关系、存储方式和处理方式即是数据结构。

2. 特性

算法是满足下列性质的指令序列.

• 有穷性：一个算法总是执行有穷步数后结束，且每一步都在有穷时间内完成。
• 确定性：算法中每条指令必须有确切含义，没有二义性，只有唯一一条执行路径。对于相同的输入只有相同的输出。
• 可行性：算法是可执行的，其操作可以通过已经实现的基本操作执行有限次来实现。
• 输入：一个算法有零个或多个输入。
• 输出：一个算法有一个或多个输出。

3. 算法设计要求

• 正确性 correctness
  • 没有语法错误
  • 对于精心选择的，苛刻的***难的数据也能输出正确的结果
  • 程序对于一切合法的输入数据都能得到正确的输出结果
• 可读性 readability
• 健壮性 robustness
  • 指当输入非法数据的时候，算法能够恰当的做出反应或进行相应处理，而不是输出莫名其妙的结果
  • 处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或者错误性质的值，以便在更高抽象层次上进行处理
• 高效性 efficiency
  要求算法花费尽量少的时间（时间效率）和尽量低的存储需求（空间效率）。

4. 计算机问题求解步骤

1. 分析问题： 分析问题的输入、要求和输出.
2. 数据结构设计： 选择或设计能有效表示和存储问题所涉及的数据对象的、能支持算法实现的数据结构.
3. 算法设计： 选择算法策略、描述和逐步细化算法步骤.
4. 算法分析： 完善改进数据结构和算法.
5. 程序实现： 用某种编程语言定义数据结构、编写实现算法的代码并运行调试.

2. 数据结构的两种层次

2.1 逻辑结构

描述数据元素之间的逻辑关系，与数据的存储无关，独立于计算机；是从具体问题抽象出来的数学模型。

1. 线性结构

有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

例如：线性表、栈（特殊线性表）、队列（特殊线性表）、串、数组、广义表等

2. 非线性结构

一个结点可能有多个直接前趋和直接后继。

例如：树 (一对多) 和 图 (多对多)

• 集合结构：数据元素除了“同属一个集合”外没有其他关系.
• 树：数据元素存在一对多的关系. 棋盘预测分析，数据像树木一样展开
• 图：数据元素存在多对多关系. 地图最短路径，数据像一张网格一样错综复杂

2.2 存储结构（物理结构）

数据元素及其关系在计算机存储器中的结构（存储方式）。

1. 顺序存储结构

用一组连续的存储单元依次存放数据。数据元素之间的逻辑关系由元素的存储位置来表示
C语言中的数组、C++中的vector容器都是顺序存储结构

• 优点： 实现随机存取、每个元素占用最少的存储空间
• 缺点： 只能使用相邻的一整块存储单元，可能产生较多的外部碎片

2. 链式存储结构

存储空间不连续，元素之间的逻辑关系用结点的指针表示。

• 优点： 不会出现碎片现象，充分利用所有存储单元。在表示各种逻辑结构时往往比顺序结构更加方便。
• 缺点： 指针额外占用存储空间、只能实现顺序存取。

3. 索引存储结构

建立附加的索引表，其中每项称为索引项

• 优点： 检索速度快。
• 缺点； 索引表额外占用存储空间。增删数据也要修改索引表

4. 散列(哈希)存储结构

根据元素的关键字直接计算出该元素的存储地址

• 优点： 检索、增删改查结点的操作都很快。
• 缺点： 若散列函数不好，可能出现存储单元冲突，解决冲突会增加时间和空间开销。

3. 算法和算法分析

3.1 时间复杂度

• 一个语句的频度是该语句在算法中被重复执行的次数。

• 算法运行时间=
  $$\sum_{
  \begin{subarray}{l}
  \end{subarray}}语句的频度×语句执行一次所需时间$$

• 算法中所有语句的频度之和记为 T(n)，它是问题规模n的函数。时间复杂度主要分析T(n)的数量级。

  算法中基本运算（最深层循环内的语句）的频度与 T(n) 同数量级。

  用 f(n) 表示算法中的基本运算的频度。

若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度（O是数量级的符号），简称时间复杂度

用 O(f(n)) 表示 f(n) 中随 n 增长最快的项，将其系数置1作为时间复杂度的度量（渐进时间复杂度）。

T(n)=O(f(n)) 如f(n)=an³+bn²，则时间复杂度为O(n^3)

::: tip 问题规模n的含义

• 循环：条件判断执行次数
• 排序：n为数组中元素个数
• 矩阵：n为矩阵阶数或行列数
• 多项式：n为多项式的项数
• 集合：n为元素个数
• 树：n为树的节点个数
• 图：n为图的顶点数或边数
  :::
  计算时间复杂度重点是找到问题规模 n 与基本语句频度 t 之间的数学关系。

::: tip 时间复杂度具体求法

• 循环主体中的变量参与循环条件的判断
  • 找出基本操作
  • 设基本操作执行次数为T(n)，根据初始条件和基本操作语句确定变量与次数的关系式
  • 带回循环条件，求出T(n)，确定O(n)
• 循环主体中的变量与循环条件无关
  • 递归程序
    • 确定递推关系（注意这里确定的是基本操作次数的递推关系，不要和变量的值搞混）
    • 推出递推关系与执行次数的表达式
    • 令低级递推关系中的次数为常数（0或1），整理式子
    • 推导出T(n)
  • 非递归程序
    • 等比、等差数列求和
      :::

平均时间复杂度A(n)

• 最坏情况下的时间复杂度W(n).
  算法求解输入规模为 n 的实例所需要的最长时间.
• 平均状况下的时间复杂度A(n).
  在给定同样规模为 n 的输入实例的概率分布下，算法求解这些实例所需要的平均时间.
  设 S 是规模为 n 的实例集，实例 I∈S 的概率是 P_I
  算法对实例I执行的基本运算次数是 t_I
  
  在某些情况下可以假定每个输入实例概率相等.

---

example1

x=0,y=0                  //1次    
for(int k=0;k<n;k++)     //n+1(判断语句执行n+1，循环体执行n)
    x++;                 //n 
for(int i=0;i<n;i++)     //n+1
    for(int j=0;j<n;j++) //n(n+1)
        y++;             //n*n

T(n)=O(n^2)

---

example2

for (i=1;i<n;i++)         //
    for (j=1;j<=i;j++)
        for (k=1;k<=j;k++)
            x=x+1;

第二重是 j 到 i，j是变量，相当于 1+2+3+…+i 等于i*（i+1）/2

---

example3

i=1;
while (i<=n)
    i=i*2;//找出基本运算

设循环体执行次数为 $x$ ，令 $2^x≤n$，得$x≤log_2n$
$T(n)=O(log_2n)$

---

有时，$f(n)$（基本操作执行次数）随问题的输入数据集的不同而不同。

::: tip 加法规则和乘法规则
将复杂算法分解为几个部分，有

• 顺序：T(n)=T1(n)+T2(n)=O(max(f(n)+g(n)))
• 嵌套、循环：T(n)=T1(n)*T2(n)=O(f(n) * g(n))
  :::

渐进时间复杂度按递增顺序：
O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n^k) < O(2^n) < O(n!) < O(n^n)

3.2 空间复杂度

空间复杂度：该算法所耗费的存储空间，它是问题规模n的函数。
S(n)=O(g(n)).