数据结构第一章：算法时间复杂度分析和算法设计的基本方法

一、本章核心知识回顾

数据结构主要研究三方面：

1. 数据的逻辑结构（集合、线性、树、图）
2. 数据的存储结构（顺序、链接、索引、散列）
3. 数据的运算（算法）（查找、排序、插入、删除、修改、遍历）

算法 是解决特定问题的步骤描述，五个特性：有穷性、确定性、可行性、输入、输出。
好算法 的标准：正确性、可读性、健壮性、高效（时间、空间）。

时间复杂度 是算法运行时间随问题规模 (n) 增长的趋势，用大 O 表示：
[
T(n)=O(f(n))
]
通常取基本操作重复执行的次数，忽略常数和低阶项。

空间复杂度 类似，是临时占用存储空间的量度。

---

二、如何分析语句频度和时间复杂度？（作业 1~3 关键）

1. 基本方法

• 语句频度：某条语句在算法执行过程中一共运行了多少次。
• 时间复杂度：找出基本操作（通常是内层循环体的操作），计算其执行次数 (T(n))，然后取最高阶得到 (O(f(n)))。

2. 常见循环结构的时间复杂度

循环形式	时间复杂度	说明
单层循环，循环次数 (n)	(O(n))
双层嵌套，每层 (n)	(O(n^2))
三层嵌套，每层 (n)	(O(n^3))
循环次数与对数相关（如 (k=k*2)）	(O(\log n))
循环次数与平方根相关	需具体分析

3. 典型例题（非作业原题）

例题 1：求以下代码中语句 x++ 的频度和时间复杂度。

for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
        x++;

• 内层循环 j 从 0 到 i-1，当 i=0 时执行 0 次，i=1 时 1 次，……，i=n-1 时 n-1 次。
• 总次数 = (0 + 1 + 2 + ... + (n-1) = \frac{n(n-1)}{2})。
• 时间复杂度：(O(n^2))。

例题 2：分析以下代码的时间复杂度。

for (i = 1; i <= n; i *= 2)
    for (j = 1; j <= n; j++)
        x++;

• 外层循环 i 按倍数增长：1, 2, 4, ..., 最多 ( \log_2 n ) 次。
• 内层循环每次都执行 (n) 次。
• 总次数 ( \approx n \log_2 n )，时间复杂度 (O(n \log n))。

例题 3：分析条件循环（类似作业第 2 题）。

for (i = 1; i <= n; i++) {
    if (i % 2 == 0) {
        for (j = i; j <= n; j++)
            x++;
    }
}

• 只有当 i 为偶数时，内层循环才执行。
• 内层执行次数 = 所有偶数 i 对应的 (n - i + 1) 之和。
• 设 (i = 2k)，则 (k) 从 1 到 (\lfloor n/2 \rfloor)，次数为 (\sum_{k=1}^{\lfloor n/2 \rfloor} (n - 2k + 1))，化简后最高次项为 (O(n^2))。

关键技巧：遇到分支结构，计算所有可能进入分支时的总次数，忽略常数系数和低阶项。

---

三、如何编写算法求“最大和次大元素”？（作业 4 准备）

1. 算法思想（非原题，但类似）

问题：给定一个整数数组，找出最大值和第二大值（次大值）。

高效方法（一趟扫描）：

• 初始化 max1 和 max2 为数组前两个元素，并确保 max1 >= max2。
• 从第三个元素开始遍历：
  • 若当前元素 > max1，则更新 max2 = max1，max1 = 当前元素；
  • 否则若当前元素 > max2，则更新 max2 = 当前元素。
• 考虑数组长度小于 2 的特殊情况。

为什么高效？ 只遍历一次数组，时间复杂度 (O(n))。

2. C 语言实现（示例，非作业原题）

#include <stdio.h>

void findMaxTwo(int arr[], int n, int *max1, int *max2) {
    if (n < 2) {
        // 处理异常，可设置特殊值
        return;
    }
    // 初始设定
    if (arr[0] >= arr[1]) {
        *max1 = arr[0];
        *max2 = arr[1];
    } else {
        *max1 = arr[1];
        *max2 = arr[0];
    }
    for (int i = 2; i < n; i++) {
        if (arr[i] > *max1) {
            *max2 = *max1;
            *max1 = arr[i];
        } else if (arr[i] > *max2) {
            *max2 = arr[i];
        }
    }
}

int main() {
    int a[] = {5, 2, 9, 1, 7, 6};
    int max1, max2;
    findMaxTwo(a, 6, &max1, &max2);
    printf("最大: %d, 次大: %d\n", max1, max2);
    return 0;
}

3. 时间复杂度分析（通用）

• 最好情况：数组本身前两个元素就是最大和次大，后续无需更新？不对，因为后续还可能更大，所以仍然要遍历所有元素，扫描次数始终为 (n)，每个元素常数次比较。
• 最坏情况：同样需要遍历所有元素，每个元素比较次数也固定（最多两次比较）。
• 因此，最好和最坏情况时间复杂度均为 (O(n))（与数组的排列顺序无关）。
• 若要求平均情况，也是 (O(n))。

注意：有些算法（如先排序再取前两个）可能时间复杂度更高（如 (O(n\log n))），所以我们的算法更高效。

---

四、现在，请你尝试完成作业

作业 1、2、3 的思路引导

• 第 1 题：属于典型的三重循环，内层循环次数与 n 直接相关。
  步骤：

  1. 统计每条语句的执行次数（可用求和公式）。
  2. 基本操作（语句 5）的执行次数为 (n \times n \times n = n^3)，所以时间复杂度为 (O(n^3))。
  3. 写出详细的求和过程（如 (\sum{i=0}^{n-1}\sum{j=0}^{n-1}\sum_{k=0}^{n-1} 1 = n^3)）。

• 第 2 题：外层循环 i 从 1 到 n，但内层循环只有满足 3*i <= n 时才执行。
  步骤：

  1. 找出所有满足条件的 i：当 i <= n/3 时内层执行。
  2. 内层循环 j 从 3*i 到 n，次数为 n - 3*i + 1。
  3. 求和：(\sum_{i=1}^{\lfloor n/3 \rfloor} (n - 3i + 1))，化简后得到最高次项为 (O(n^2))。

• 第 3 题：外层两层循环，内层 while 循环每次 k 乘以 5，直到超过 n。
  步骤：

  1. 内层 while 的执行次数：若 k 初始为 1，则 k 变为 5, 25, ... 直到超过 n，次数为 (\lfloor \log_5 n \rfloor + 1)，即 (O(\log n))。
  2. 外层两层循环分别是 i 和 j，各执行 n 次，所以总次数为 (n^2 \times O(\log n) = O(n^2 \log n))。

作业 4 的注意点

• 算法思想用自然语言描述（如“一趟扫描，维护最大和次大”）。
• C 语言代码清晰，注意处理数组长度小于 2 的情况（可返回特殊值或报错）。
• 时间复杂度分析时，说明最好和最坏情况都是 (O(n))，因为无论如何都要遍历所有元素。

---

五、总结 & 学习建议

• 熟记 Big-O 定义：忽略常数因子和低阶项，关注最高阶。
• 会求语句频度：用求和公式，并化简。
• 会写简单算法：一趟扫描、双指针等是常见技巧。
• 分析时间复杂度时，要考虑所有可能执行的分支，取总次数。