基本概念

解决问题方法的效率

• 跟数据的组织方式有关

• 跟空间的利用率有关

• 跟算法的巧妙程度有关

1. 什么是数据结构

• 数据对象在计算机中的组织方式

  • 逻辑结构

    • 线性、树、图

  • 物理存储结构

    • 顺序存储、链式存储

• 数据对象必定与一系列加在其上的操作相关联

• 完成这些操作所用的方法就是算法

1.1 数据类型

• 数据对象集

• 数据集合相关联的操作集

例：整型（操作集：加减乘除；数据对象集：所有整型数）

1.2 抽象数据类型

抽象

描述数据类型的方法不依赖与具体实现

• 与存放数据的机器无关

• 与数据存储的物理结构无关

• 与实现操作的算法和编程语言均无关

只描述数据对象集和相关操作集 是什么，并不涉及 如何做到 的问题

例：矩阵 的抽象数据类型的定义

• 类型名称：矩阵（ $Matrix$ ）

• 数据对象集：一个 $M \times N$ 的矩阵 $A_{M \times N} = (a_{ij}) (i = 1, \cdots , M ; j = 1, \cdots , N)$ 由 $M \times N$ 个三元组 $<a, i, j>$ 构成，其中 $a$ 是矩阵元素的值，$i$ 是元素所在的行号， $j$ 是元素所在的列号。

• 操作集：对于任意矩阵 $A、B、C \in Matrix$ ，以及整数 $i、j、M、N$

  • Matrix Create(int M, int N)：返回一个 $M \times N$ 的矩阵；

  • int GetMaxRow(Matrix A)：返回矩阵$A$ 的总行数；

  • int GetMaxCol(Matrix A)：返回矩阵$A$ 的总列数；

  • ElementType GetEntry(Matrix A, int i, int j)：返回矩阵$A$ 的第 $i$ 行、第 $j$ 列元素；

  • Matrix Add(Matrix A, Matrix B)：如果 $A$ 和 $B$ 的行、列数一致，则返回矩阵 $C = A + B$ ，否则返回错误标志；

  • Matrix Multiply(Matrix A, Matrix B)：如果 $A$ 的列数等于 $B$ 的行数，则返回矩阵 $C = AB$ ，否则返回错误标志；

  • $\cdots \cdots$

2. 什么是算法

• 一个有限指令集

• 接受一些输入（有些情况下不需要输入）

• 产生输出

• 一定在有限步骤之后终止

• 每一条指令必须

  • 有充分明确的目标，不可以有歧义

  • 计算机能处理的范围之内

  • 描述应不依赖于任何一种计算机语言以及具体的实现手段

2.1 什么是好的算法

• 空间复杂度 $S(n)$

  • 根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中的。

• 时间复杂度 $T(n)$

  • 根据算法写成的程序在执行时耗费时间的长度。这个长度也往往与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

在分析一般算法的效率时，我们经常关注下面两种复杂度

• 最坏情况复杂度 $T_{worst}(n)$

• 平均复杂度 $T_{avg}(n)$

• 关系： $T_{avg}(n) \le T_{worst}(n)$

复杂度的渐进表示法

• $T(n) = O(f(n))$ 表示存在常数 $C > 0, n_0 > 0$ 使得当 $n \ge n_0$ 时有 $T(n) \le C \cdot f(n)$

• $T(n) = \Omega (g(n))$ 表示存在常数 $C > 0, n_0 > 0$ 使得当 $n \ge n_0$ 时有 $T(n) \ge C \cdot g(n)$

• $T(n) = \Theta (h(n))$ 表示同时有 $T(n) = O(h(n))$ 和 $T(n) = \Omega (h(n))$

复杂度分析小窍门

• 若两段算法分别有复杂度 $T_1(n) = O(f_1(n))$ 和 $T_2(n) = O(f_2(n))$

  • $T_1(n) + T_2(n) = max (O(f_1(n)), O(f_2(n)))$

  • $T_1(n) \times T_2(n) = O(f_1(n)) \times O(f_2(n))$