# 数据结构与算法基础及复杂度分析

## 一、 数据结构与算法概述

无论是解决现实生活中的实际问题，还是在算法竞赛中折桂，编写程序一般都需要处理好以下两个核心方面：

1. **用什么样的结构保存数据**（数据结构）
2. **用什么样的步骤处理数据并解决问题**（算法）

### 1.1 什么是数据结构？
**数据结构（Data Structure）**是专门研究数据的表示、类型以及它们之间关系的学科。它决定了数据如何存储在内存中，以及如何高效地访问和操作这些数据。

要想在计算机中解决现实问题，必须先用相应的数据把问题模型表示出来，保存在内存中，才能通过特定的算法去处理并输出结果。常见的数据结构包括：
* **线性结构**：数组（Array）、链表（Linked List）、栈（Stack）、队列（Queue）
* **非线性结构**：树（Tree）、图（Graph）

### 1.2 什么是算法？
**算法（Algorithm）**是解决问题的具体步骤或指令集，它描述了如何一步步处理数据以达到预期结果。算法与数据结构关系紧密：在设计算法时通常需要先确定数据结构；而在讨论某种数据结构时，也必然会涉及在其上运行的相应算法。

---

## 二、 算法复杂度评估

评价一个算法的优劣，通常从以下两个维度进行判别：

1. **时间复杂度（Time Complexity）**：评估程序执行所需的时间（通常通过估算基本操作的执行次数来体现），用以衡量算法对 CPU 资源的占用程度。
2. **空间复杂度（Space Complexity）**：评估程序执行所需的内存空间，用以衡量算法对物理内存的占用程度。

> **提示**：在实际应用和算法竞赛中，我们通常更关注**时间复杂度**，因为它往往是决定程序是否会运行超时（TLE）的关键。因此，当行业中只提到“复杂度”时，通常默认指“时间复杂度”。

---

## 三、 复杂度分析实例：计算多项式的值

一个算法无论多复杂，都可以分解为具体的简单操作（如算术运算、关系运算、逻辑运算等）。我们通过一个经典的数学问题来说明如何分析不同算法的复杂度：

**【问题描述】**
已知 $x$ 的值，并输入 $n$ 次多项式的各项系数 $a_i$（其中 $0 \le i \le n$），求多项式 $y$ 的值：
$$y = a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + \dots + a_1 x + a_0$$

---

### 算法一：模拟法（直接求解）
最直接的思路是按照多项式的定义，先计算每一项 $a_i x^i$ 的值，然后再累加到结果 $y$ 中。计算 $x^i$ 时，通过循环累乘 $i$ 次 $x$ 来实现。

#### 代码实现
=== "C++"
    ```cpp
    // 假设各项系数存放在数组 a 中，a[i] 对应 a_i
    double y = a[0];
    for (int i = 1; i <= n; i++) {
        double t = a[i];
        for (int k = 1; k <= i; k++) {
            t *= x;  // 循环累乘 i 次计算 a_i * x^i
        }
        y += t;
    }
    cout << y << "\n";
    ```

=== "Python"
    ```python
    # 假设各项系数存放在列表 a 中，a[i] 对应 a_i
    y = a[0]
    for i in range(1, n + 1):
        t = a[i]
        for k in range(1, i + 1):
            t *= x  # 循环累乘 i 次计算 a_i * x^i
        y += t
    print(y)
    ```

#### 复杂度分析
* **乘法运算**：第 5 行的内循环在计算 $a_i x^i$ 时执行了 $i$ 次乘法。因此，计算 $y$ 整体所需的乘法次数为：
  $$1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2} \text{ 次}$$
* **加法运算**：外循环中累加到 $y$ 贡献了 $n$ 次加法。
* **总运算量**：忽略赋值与循环控制开销，总算术运算次数大约为 $\frac{n(n + 3)}{2}$ 次。

---

### 算法二：递推法（利用前一项结果）
在算法一中，每次计算 $x^i$ 都是从 $1$ 开始累乘，这造成了极大的重复计算。
实际上，由 $x^i = x \cdot x^{i-1}$ 可知，当前项的 $x^i$ 可以在前一项 $x^{i-1}$ 的基础上直接乘以 $x$ 得到。我们可以引入一个变量 `current_x` 来存储并递推这一中间值。

#### 代码实现
=== "C++"
    ```cpp
    // 假设各项系数存放在数组 a 中
    double y = a[0];
    double current_x = 1.0;
    for (int i = 1; i <= n; i++) {
        current_x *= x;          // 递推计算 x^i
        y += a[i] * current_x;   // 1 次乘法和 1 次加法
    }
    cout << y << "\n";
    ```

=== "Python"
    ```python
    # 假设各项系数存放在列表 a 中
    y = a[0]
    current_x = 1.0
    for i in range(1, n + 1):
        current_x *= x
        y += a[i] * current_x
    print(y)
    ```

#### 复杂度分析
* **乘法运算**：每轮循环包含 $2$ 次乘法（计算 `current_x` 和计算 $a_i \cdot x^i$），共计 $2n$ 次乘法。
* **加法运算**：共计 $n$ 次加法。
* **总运算量**：总算术运算次数大约为 $3n$ 次。相比模拟法，运算量从 $O(n^2)$ 降低到了 $O(n)$。

---

### 算法三：秦九韶 - 霍纳算法（Horner's Rule）
南宋时期的中国数学家秦九韶与英国数学家霍纳（Horner）提出了更为巧妙的多项式计算算法。他们将原本的展开式改写成嵌套相乘的形式：
$$y = \left( \dots \left( \left( a_n x + a_{n-1} \right) x + a_{n-2} \right) x + \dots + a_1 \right) x + a_0$$

#### 实例说明
计算多项式：$y = 7x^5 + 4x^4 - 8x^3 + 6x + 2$。
已知系数为：$a_5=7, a_4=4, a_3=-8, a_2=0, a_1=6, a_0=2$。
改写为嵌套结构：
$$y = \left( \left( \left( \left( 7x + 4 \right) x - 8 \right) x + 0 \right) x + 6 \right) x + 2$$

#### 代码实现
=== "C++"
    ```cpp
    double y = a[n];
    for (int i = n - 1; i >= 0; i--) {
        y = y * x + a[i];  // 每步仅需 1 次乘法和 1 次加法
    }
    cout << y << "\n";
    ```

=== "Python"
    ```python
    y = a[n]
    for i in range(n - 1, -1, -1):
        y = y * x + a[i]
    print(y)
    ```

#### 复杂度分析
* **总运算量**：该算法在计算时，循环仅执行 $n$ 次，每轮循环只需 $1$ 次乘法和 $1$ 次加法。总计仅需 $n$ 次乘法和 $n$ 次加法（共约 $2n$ 次运算），是计算多项式值的最优算法。

---

## 四、 渐进时间复杂度（大 O 表示法）

一般情况下，算法中基本操作重复执行的次数是问题规模 $n$ 的某个函数 $f(n)$。对于上述三个算法，它们的 $f(n)$ 分别是：
* 模拟法：$f(n) = \frac{n^2 + 3n}{2}$
* 递推法：$f(n) = 3n$
* 秦九韶算法：$f(n) = 2n$

为了直观地度量算法随问题规模 $n$ 增大时的运行时间增长趋势，我们将算法的执行时间度量 $T(n)$ 记作：
$$T(n) = O(f(n))$$

这被称为算法的**渐进时间复杂度（Asymptotic Time Complexity）**，简称**时间复杂度**。

在大 O 表示法中，我们只关注随 $n$ 趋于无穷大时起决定性作用的最高阶项，并忽略其系数和低阶项。例如：
* 模拟法的基本操作次数为 $\frac{1}{2}n^2 + \frac{3}{2}n$，当 $n$ 变得极大时，$n^2$ 项的增长速度远超 $n$ 项。因此，其渐进时间复杂度表示为 **$O(n^2)$**。
* 递推法和秦九韶算法的时间复杂度均为 **$O(n)$**。

---

## 五、 常见复杂度级别与增长趋势

根据算法运行时间随数据规模增长的快慢，我们可以将算法分为两大类：

### 5.1 多项式时间算法（Polynomial-time Algorithm）
这类算法的运行时间受限于 $n$ 的多项式。在实际开发中，这些是属于“可行”或“高效”的算法。常见的优劣关系为：
$$O(1) < O(\log_2 n) < O(n) < O(n \log_2 n) < O(n^2) < O(n^3)$$

* **$O(1)$ 常数级**：执行时间不随数据规模 $n$ 改变。
* **$O(\log_2 n)$ 对数级**：每次迭代规模减半（如二分查找）。
* **$O(n)$ 线性级**：运行时间与数据规模成正比。
* **$O(n \log_2 n)$ 线性对数级**：高效排序算法的通用复杂度（如归并排序、快速排序）。
* **$O(n^2)$ 平方级**、**$O(n^3)$ 立方级**：多重循环嵌套，适合小规模数据。

### 5.2 指数时间算法（Exponential-time Algorithm）
这类算法的运行时间随 $n$ 的增长呈爆炸式飙升，通常只适用于极小规模的数据。其关系为：
$$O(2^n) < O(n!) < O(n^n)$$

* **$O(2^n)$ 指数级**：如求解汉诺塔问题、暴力的子集生成。
* **$O(n!)$ 阶乘级**：如全排列生成、旅行商问题（TSP）的暴力求解。
![](https://cdn.hlcoding.com/media/blog/2026-08-21/1aae263f86024962b51d666dc2a52ed0_1787284016.png)
> **图 1 - 复杂度增长趋势对比**
> 当数据规模 $n$ 增大时，不同复杂度的执行次数增长极快。例如，当 $n = 100$ 时，$O(n)$ 仅需 100 次操作，而 $O(n^2)$ 需要 10,000 次操作。对于指数级 $O(2^n)$，其操作次数已是天文数字（$\approx 1.26 \times 10^{30}$），任何现代计算机都无法在可接受的时间内运行完毕。因此，设计算法时应尽可能将复杂度控制在多项式级别内。

数据结构与算法基础及复杂度分析

一、数据结构与算法概述

无论是解决现实生活中的实际问题，还是在算法竞赛中折桂，编写程序一般都需要处理好以下两个核心方面：

用什么样的结构保存数据（数据结构）
用什么样的步骤处理数据并解决问题（算法）

1.1 什么是数据结构？

数据结构（Data Structure）是专门研究数据的表示、类型以及它们之间关系的学科。它决定了数据如何存储在内存中，以及如何高效地访问和操作这些数据。

要想在计算机中解决现实问题，必须先用相应的数据把问题模型表示出来，保存在内存中，才能通过特定的算法去处理并输出结果。常见的数据结构包括： * 线性结构：数组（Array）、链表（Linked List）、栈（Stack）、队列（Queue） * 非线性结构：树（Tree）、图（Graph）

1.2 什么是算法？

算法（Algorithm）是解决问题的具体步骤或指令集，它描述了如何一步步处理数据以达到预期结果。算法与数据结构关系紧密：在设计算法时通常需要先确定数据结构；而在讨论某种数据结构时，也必然会涉及在其上运行的相应算法。

二、算法复杂度评估

评价一个算法的优劣，通常从以下两个维度进行判别：

时间复杂度（Time Complexity）：评估程序执行所需的时间（通常通过估算基本操作的执行次数来体现），用以衡量算法对 CPU 资源的占用程度。
空间复杂度（Space Complexity）：评估程序执行所需的内存空间，用以衡量算法对物理内存的占用程度。

提示：在实际应用和算法竞赛中，我们通常更关注时间复杂度，因为它往往是决定程序是否会运行超时（TLE）的关键。因此，当行业中只提到“复杂度”时，通常默认指“时间复杂度”。

三、复杂度分析实例：计算多项式的值

【问题描述】 已知 $x$ 的值，并输入 $n$ 次多项式的各项系数 $a_i$（其中 $0 \le i \le n$），求多项式 $y$ 的值： $$y = a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + \dots + a_1 x + a_0$$

算法一：模拟法（直接求解）

最直接的思路是按照多项式的定义，先计算每一项 $a_i x^i$ 的值，然后再累加到结果 $y$ 中。计算 $x^i$ 时，通过循环累乘 $i$ 次 $x$ 来实现。

代码实现

=== "C++" cpp // 假设各项系数存放在数组 a 中，a[i] 对应 a_i double y = a[0]; for (int i = 1; i <= n; i++) { double t = a[i]; for (int k = 1; k <= i; k++) { t *= x; // 循环累乘 i 次计算 a_i * x^i } y += t; } cout << y << "\n";

=== "Python" python # 假设各项系数存放在列表 a 中，a[i] 对应 a_i y = a[0] for i in range(1, n + 1): t = a[i] for k in range(1, i + 1): t *= x # 循环累乘 i 次计算 a_i * x^i y += t print(y)

复杂度分析

乘法运算：第 5 行的内循环在计算 $a_i x^i$ 时执行了 $i$ 次乘法。因此，计算 $y$ 整体所需的乘法次数为： $$1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2} \text{ 次}$$
加法运算：外循环中累加到 $y$ 贡献了 $n$ 次加法。
总运算量：忽略赋值与循环控制开销，总算术运算次数大约为 $\frac{n(n + 3)}{2}$ 次。

算法二：递推法（利用前一项结果）

在算法一中，每次计算 $x^i$ 都是从 $1$ 开始累乘，这造成了极大的重复计算。实际上，由 $x^i = x \cdot x^{i-1}$ 可知，当前项的 $x^i$ 可以在前一项 $x^{i-1}$ 的基础上直接乘以 $x$ 得到。我们可以引入一个变量 current_x 来存储并递推这一中间值。

代码实现

=== "C++" cpp // 假设各项系数存放在数组 a 中 double y = a[0]; double current_x = 1.0; for (int i = 1; i <= n; i++) { current_x *= x; // 递推计算 x^i y += a[i] * current_x; // 1 次乘法和 1 次加法 } cout << y << "\n";

=== "Python" python # 假设各项系数存放在列表 a 中 y = a[0] current_x = 1.0 for i in range(1, n + 1): current_x *= x y += a[i] * current_x print(y)

复杂度分析

乘法运算：每轮循环包含 $2$ 次乘法（计算 current_x 和计算 $a_i \cdot x^i$），共计 $2n$ 次乘法。
加法运算：共计 $n$ 次加法。
总运算量：总算术运算次数大约为 $3n$ 次。相比模拟法，运算量从 $O(n^2)$ 降低到了 $O(n)$。

算法三：秦九韶 - 霍纳算法（Horner's Rule）

南宋时期的中国数学家秦九韶与英国数学家霍纳（Horner）提出了更为巧妙的多项式计算算法。他们将原本的展开式改写成嵌套相乘的形式： $$y = \left( \dots \left( \left( a_n x + a_{n-1} \right) x + a_{n-2} \right) x + \dots + a_1 \right) x + a_0$$

实例说明

计算多项式：$y = 7x^5 + 4x^4 - 8x^3 + 6x + 2$。已知系数为：$a_5=7, a_4=4, a_3=-8, a_2=0, a_1=6, a_0=2$。改写为嵌套结构： $$y = \left( \left( \left( \left( 7x + 4 \right) x - 8 \right) x + 0 \right) x + 6 \right) x + 2$$

代码实现

=== "C++" cpp double y = a[n]; for (int i = n - 1; i >= 0; i--) { y = y * x + a[i]; // 每步仅需 1 次乘法和 1 次加法 } cout << y << "\n";

=== "Python" python y = a[n] for i in range(n - 1, -1, -1): y = y * x + a[i] print(y)

复杂度分析

总运算量：该算法在计算时，循环仅执行 $n$ 次，每轮循环只需 $1$ 次乘法和 $1$ 次加法。总计仅需 $n$ 次乘法和 $n$ 次加法（共约 $2n$ 次运算），是计算多项式值的最优算法。

四、渐进时间复杂度（大 O 表示法）

一般情况下，算法中基本操作重复执行的次数是问题规模 $n$ 的某个函数 $f(n)$。对于上述三个算法，它们的 $f(n)$ 分别是： * 模拟法：$f(n) = \frac{n^2 + 3n}{2}$ * 递推法：$f(n) = 3n$ * 秦九韶算法：$f(n) = 2n$

为了直观地度量算法随问题规模 $n$ 增大时的运行时间增长趋势，我们将算法的执行时间度量 $T(n)$ 记作： $$T(n) = O(f(n))$$

这被称为算法的渐进时间复杂度（Asymptotic Time Complexity），简称时间复杂度。

在大 O 表示法中，我们只关注随 $n$ 趋于无穷大时起决定性作用的最高阶项，并忽略其系数和低阶项。例如： * 模拟法的基本操作次数为 $\frac{1}{2}n^2 + \frac{3}{2}n$，当 $n$ 变得极大时，$n^2$ 项的增长速度远超 $n$ 项。因此，其渐进时间复杂度表示为 $O(n^2)$。 * 递推法和秦九韶算法的时间复杂度均为 $O(n)$。

五、常见复杂度级别与增长趋势

根据算法运行时间随数据规模增长的快慢，我们可以将算法分为两大类：

5.1 多项式时间算法（Polynomial-time Algorithm）

这类算法的运行时间受限于 $n$ 的多项式。在实际开发中，这些是属于“可行”或“高效”的算法。常见的优劣关系为： $$O(1) < O(\log_2 n) < O(n) < O(n \log_2 n) < O(n^2) < O(n^3)$$

$O(1)$ 常数级：执行时间不随数据规模 $n$ 改变。
$O(\log_2 n)$ 对数级：每次迭代规模减半（如二分查找）。
$O(n)$ 线性级：运行时间与数据规模成正比。
$O(n \log_2 n)$ 线性对数级：高效排序算法的通用复杂度（如归并排序、快速排序）。
$O(n^2)$ 平方级、$O(n^3)$ 立方级：多重循环嵌套，适合小规模数据。

5.2 指数时间算法（Exponential-time Algorithm）

这类算法的运行时间随 $n$ 的增长呈爆炸式飙升，通常只适用于极小规模的数据。其关系为： $$O(2^n) < O(n!) < O(n^n)$$

$O(2^n)$ 指数级：如求解汉诺塔问题、暴力的子集生成。
$O(n!)$ 阶乘级：如全排列生成、旅行商问题（TSP）的暴力求解。

图 1 - 复杂度增长趋势对比 当数据规模 $n$ 增大时，不同复杂度的执行次数增长极快。例如，当 $n = 100$ 时，$O(n)$ 仅需 100 次操作，而 $O(n^2)$ 需要 10,000 次操作。对于指数级 $O(2^n)$，其操作次数已是天文数字（$\approx 1.26 \times 10^{30}$），任何现代计算机都无法在可接受的时间内运行完毕。因此，设计算法时应尽可能将复杂度控制在多项式级别内。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com