数据结构与算法入门

一、数据结构的基本概念

1、基本概念

数据结构（Data Structure）是一种存储和组织数据的方式，旨在便于访问和修改。在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素相互之间的关系称为结构。

下面介绍一些数据结构中常用的术语：

• 数据：是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符合的集合。数据是计算机程序加工的原料。
• 数据元素：是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成，数据项是构成数据元素的不可分割的最小单位。如学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。
• 数据对象：是具有相同性质的数据元素的集合，是数据的一个子集。
• 数据类型：是一个值的集合和定义在此集合上的一组操作的总称，包括原子类型、结构类型和抽象数据类型。

数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。下面我们将对这三方面的内容进行详细介绍。

2、数据结构的三要素

（1）逻辑结构

• 概念：是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。

• 分类：分为线性结构和非线性结构。下面用一张图来介绍数据的逻辑结构分类：
  

（2）存储结构

• 概念：是指数据结构在计算机中的存储表示（又称映像），也称为物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是用计算机语言实现的逻辑结构，它依赖于计算机语言。

• 分类：主要有顺序存储、链式存储、索引存储和散列存储。下面通过表格来介绍一下这几种存储结构：

  存储结构	解释	优点	缺点
  顺序存储	把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。	可以实现随机存取，每个元素占用最少的存储空间。	只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
  链式存储	不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。	不会出现碎片现象，能充分利用所有存储单元。	每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。
  索引存储	在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引的一般形式是（关键字，地址）。	检索速度快。	附加的索引表额外占用存储空间。此外增加和删除数据也要修改索引表，因而会花费较多的时间。
  散列存储	根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。	检索、增加和删除结点的操作都很快。	若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

（3）数据的运算

• 概念：施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

二、算法的基本概念

1、基本概念

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

2、算法的特性

一个算法具有下列5个重要特性：

• 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
• 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
• 可行性：算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
• 输入：一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。
• 输出：一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。

3、需达到的目标

通常，一个好的算法应考虑达到以下目标：

• 正确性：在合理的数据输入下，能够在有限的运行时间内得到正确的结果。

• 可读性：一个好的算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法易于隐藏错误，且难于调试和修改。

• 健壮性：当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。

• 高效性：高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。

4、算法效率的度量

算法效率的度量可通过时间复杂度和空间复杂度来描述的，下面将详细介绍这两种度量方法。

（1）时间复杂度

不考虑计算机的软硬件等环境因素，影响算法时间代价的最主要因素是问题规模。问题规模是算法求解问题输人量的多少，是问题大小的本质表示，一般用整数 n 表示。问题规模 n 对不同的问题含义不同，例如，在排序运算中 n 为参加排序的记录数，在矩阵运算中 n 为矩阵的阶数，在多项式运算中 n 为多项式的项数，在集合运算中 n 为集合中元素的个数，在树的有关运算中 n 为树的结点个数，在图的有关运算中 n 为图的顶点数或边数。显然，n 越大算法的执行时间越长。

一个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。

一条语句的重复执行次数称作语句频度（Frequency Count）。

例如有一个求两个 n 阶矩阵乘积的算法，代码如下：

for (i = 1; i <= n; i++) // 频度为: n + 1
{
    for (j = 1; j <= n; j++) // 频度为: n * (n + 1)
    {
        matrix[i][j] = 0; // 频度为: n^2
        for (k = 1; k <= n; k++) // 频度为: n^2 * n * (n + 1)
            matrix[i][j] = matrix[i][j] + m1[i][k] * m2[k][j];// 频度为: n^3
    }
}

该算法中所有的语句频度之和是矩阵阶数 n 的函数，用 f(n) 表示。即：

$$
f(n) = 2n^3 + 3n^2 + 2n + 1
$$

上面例子中的算法比较简单，所以我们可以直接计算出算法中所有语句的频度，但如果算法比较复杂，计算起来就比较困难。因此我们可以使用一些简化的抽象来使算法的分析更加容易。

通过分析可以发现，实际上算法中那些重复执行次数与算法执行时间成正比的语句对算法的运行时间贡献最大。以上面的例子来说就是 2n^3 这一项比 3n^2、2n、1 对算法的运行时间贡献最大。换句话说，我们真正感兴趣的是运行时间的增长率或增长量级，那么如何知道运行时间的增长量级呢？我们可以通过求对运行时间贡献最大语句在问题规模充分大（即 n 趋近于无穷）时执行次数的阶来获取。接着上面的例子，当 n 趋近于无穷时显然有：

$$
lim_{n\to+\infty} f(n) / n^3 = lim_{n\to+\infty} (2n^3 + 3n^2 + 2n + 1) / n^3 = 2
$$

即当 n 趋近于无穷时 f(n) 和 n^3 是同一个数量级（Order of Magnitude），实际上就是多项式中的最高阶项。在这里我们使用 O 来表示数量级，记作 *T(n)=O(f(n))=O(n^3)*。由此我们可以给出时间复杂度的定义。

一般情况下，算法中基本语句重复执行的次数是问题规模 n 的函数 f(n) ，算法的时间量度记作：

$$
T(n) = O(f(n))
$$

其中数学符号 O 的严格定义如下：

$$
若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n) = O(f(n))表示在存在正的常数C和n_0，使得当n \geq n_0时都满足0 \leq T(n) \leq Cf(n)。
$$

下面用一张图来说明：

由上图可知，用 O 来表示时间复杂度实际上只考虑了渐进上界。如果需要同时考虑渐进上界和下界，则可使用 Θ 来表示时间复杂度，记作 Θ(n^3) ，读作（theta n 三次方），Θ 被称为渐进记号。关于时间复杂度的详细内容，请参阅《算法导论》第三章的相关内容。

算法的时间复杂度不仅依赖于问题的规模 n，也取决于待输入数据的性质，因此时间复杂度可能并不是固定的，下面给出几种常见情况：

• 最坏时间复杂度：是指在最坏情况下算法的时间复杂度。
• 平均时间复杂度：是指所有可能输入实例在等概率出现的情况下算法的期望运行时间。
• 最好时间复杂度：是指在最好情况下算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

此外，在分析一个程序的时间复杂性时，有以下两条规则：

• 加法规则：

$$
T(n) = T_1(n) + T_2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
$$

• 乘法规则：

$$
T(n) = T_1(n) + T_2(n) = O(f(n)) \times O(g(n)) = O(f(n) \times g(n))
$$

常见的渐进时间复杂度为：

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

（2）空间复杂度

关于算法的存储空间需求,类似于算法的时间复杂度,我们采用渐近空间复杂度（Space Complexity）作为算法所需存储空间的量度，简称空间复杂度，它也是问题规模 n 的函数，记作：

$$
S(n) = O(f(n))
$$

一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。其中，对于输入数据所占的具体存储量取决于问题本身，与算法无关，这样只需分析该算法在实现时所需要的辅助空间就可以了。若算法执行时所需要的辅助空间相对于输人数据量而言是个常数，则称这个算法为原地工作，辅助空间为 *O(1)*。有的算法需要占用临时的工作单元数与问题规模 n 有关。下面将举例来进行说明：

for (i = 0; i < n/2; i++)
{
    t = a[i];
    a[i] = a[n-i-1];
    a[n-i-1] = t;
}

上述算法仅需要另外借助一个变量 t，与问题规模 n 的大小无关，所以其空间复杂度为 *O(1)*。

下面再来看一个例子：

for (i = 0; i < n; i++)
    b[i] = a[n-i-1];
for (i = 0; i < n; i++)
    a[i] = b[i];

该算法需要借助一个长度为 n 的辅助数组 b，所以其空间复杂度为 *O(n)*。

5、算法效率的取舍

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的，当追求一个较好的时间复杂度时，可能会导致占用较多的存储空间（以空间换时间），即可能会使空间复杂度的性能变差，反之亦然。不过，通常情况下，鉴于运算空间较为充足，人们都以算法的时间复杂度作为算法优劣的衡量指标。

三、算法的时间复杂度计算

1、例题

下面将通过几个例题来介绍如何计算一个算法的时间复杂度。

例题 1

现有一个程序片段如下：

x = 2;
while (x < n/2)
    x = 2 * x;

设 n 是描述问题规模的非负整数，则上述程序片段的时间复杂度为多少？

【解】

执行频率最高的语句为 x = 2 * x，每执行一次 x 乘 2。设执行次数为 t，则有：

$$
2^{t+1} < n/2
$$

所以：

$$
t < log_2(n/2) - 1 = log_2n - 2
$$

因此该程序片段的时间复杂度为：

$$
T(n) = O(log_2n)
$$

例题 2

下列函数的时间复杂度为多少？

int func(int n)
{
    int i = 0, sum = 0;
    while (sum < n)
        sum += ++i;
    return i;
}

【解】

执行频率最高的语句为 sum += ++i，它等价于 ++i; sum = sum + i;，每执行一次 i 自增 1。

i =1 时有 sum = 0 + 1；i = 2 时有 sum = 0 + 1 + 2；i = 3 时有 sum = 0 + 1 + 2 + 3。以此类推得出：

$$
sum = \frac{(1 + i)i}{2}
$$

设 t 为循环次数，则 t 满足：

$$
\frac{(1 + t)t}{2} < n
$$

因此该函数的时间复杂度为：

$$
T(n) = O(\sqrt{n})
$$

例题 3

一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别（或阶）。

式中，n 是问题的规模，为简单起见，设 n 是 2 的整数次幂。

【解】

设：

$$
n = 2^k (k \ge 0)
$$

根据题目所给的定义有：

$$
T(2^k) = 2T(2^{k-1}) + 2^k = 2^2T(2^{k-2}) + 2 \times 2^k
$$

由此可得一般递推公式为：

$$
T(2^k) = 2^iT(2^{k-i}) + i \times 2^k
$$

进而得：

$$
T(2^k) = 2^kT(2^0) + k \times 2^k
$$

因此该算法的时间复杂度为：

$$
T(n) = 2^{log_2n} + nlog_2n = n(1 + log_2n) = O(nlog_2n)
$$

2、总结

对于例题 1 和 2，需要找到执行频率最高的语句并计算它的时间复杂度，关键在于要找到执行次数与问题规模之间的函数关系，这样便可计算出时间复杂度。

对于例题 3，需要利用数学方法推出一般性的递推公式并带入特殊值进行求解，这样便可计算出时间复杂度。