一、课上练习

本节课没有课上编程练习，重点学习算法的基本概念和评价方式。

二、知识总结

✨ 算法的核心思想

算法是使用程序解决问题的方法。它是一组有限的、明确的操作步骤，用于在有限时间内解决特定问题或完成特定任务。

数据结构是数据的组织及操作方式。算法和数据结构是程序设计的两大核心，它们相辅相成——好的数据结构可以让算法更高效，好的算法也需要合适的数据结构来支撑。

✨ 算法描述

描述方式

算法可以通过以下三种方式进行描述：

1. 自然语言描述：用日常语言描述算法步骤，通俗易懂但不够精确
2. 流程图描述：用图形符号表示算法步骤和流程，直观清晰
3. 伪代码描述：介于自然语言和编程语言之间，兼顾可读性和精确性

算法描述示例

问题：如何判断一个数n是奇数还是偶数？

自然语言描述：

1. 把这个数整除2，对余数进行判断
2. 如果余数是0，则为偶数
3. 如果余数是1，则为奇数

流程图描述：

伪代码描述：

IF n % 2 == 0 THEN
    输出偶数
ELSE
    输出奇数

✨ 算法的复杂度分析

评价一个算法好坏的标准主要包括以下几个方面：

• 正确性：算法能够正确地解决问题，对所有合法输入都能产生正确输出
• 确定性：算法的每一步都有明确的含义，不存在歧义
• 可扩展性：算法能够适应不同规模的输入数据
• 时间复杂度：算法执行所需的时间（步骤数）
• 空间复杂度：算法执行过程中所需的存储空间

时间复杂度

时间复杂度描述算法执行所需要的步骤数或操作数，是衡量算法效率的重要指标。

时间复杂度的表示方法：

• 使用大O表示法描述
• 若复杂度和数据大小相关，则使用n表示数据大小

常见算法时间复杂度：

空间复杂度

空间复杂度描述算法执行过程中临时占用存储空间的大小，同样是衡量算法效率的重要指标。

空间复杂度的表示方法：

• 使用大O表示法描述
• 若复杂度和数据大小相关，则使用n表示数据大小

在竞赛中，通常更关注时间复杂度，但也需要注意空间复杂度不能超过题目给定的内存限制。

✨ 算法分析的执行示例

下面通过一个具体例子，演示如何一步步分析时间复杂度。

问题：在一个长度为n的数组中，找出所有元素对(i, j)使得 arr[i] + arr[j] == target。

1for (int i = 0; i < n; i++) {        // 外层循环执行 n 次
2    for (int j = i + 1; j < n; j++) { // 内层循环执行约 n/2 次（平均）
3        if (arr[i] + arr[j] == target) {
4            cout << i << " " << j << endl;
5        }
6    }
7}

逐步分析：

1. 当 i=0 时，内层循环执行 n-1 次
2. 当 i=1 时，内层循环执行 n-2 次
3. 当 i=2 时，内层循环执行 n-3 次
4. ...
5. 当 i=n-2 时，内层循环执行 1 次
6. 总执行次数 = (n-1) + (n-2) + ... + 1 = n(n-1)/2
7. 去掉常数和低阶项，时间复杂度为 O(n²)

对照数据规模表： O(n²) 对应的数据规模为 n<10000，所以当 n 超过 10000 时，这个算法可能会超时，需要考虑更优的解法。

✨ 算法的应用场景

• 编程竞赛（OI/ICPC）：几乎所有竞赛题都需要分析时间复杂度来选择合适的算法，避免超时。
• 软件开发：处理大数据量时，算法效率直接影响用户体验。例如搜索引擎需要在毫秒内返回结果。
• 面试与笔试：技术面试中，面试官通常会要求分析算法的时间和空间复杂度。
• 日常问题：排序、查找、路径规划等日常问题背后都有经典算法的支撑。

✨ 算法的解题步骤

拿到一道题后，如何判断该用什么复杂度的算法？

步骤1：看数据规模。 题目一般会给出 n 的范围，根据下表反推可以接受的时间复杂度：

• n ≤ 20 → 可以用 O(2ⁿ) 的暴力搜索
• n ≤ 500 → 可以用 O(n³) 的算法
• n ≤ 10000 → 需要 O(n²) 或更优
• n ≤ 100000000 → 需要 O(n) 或 O(nlogn)

步骤2：选择算法。 确定了可以接受的复杂度后，选择合适的算法来实现。

步骤3：验证。 粗略估算代码的运算次数，确保不会超过 10^8（一般情况下，1秒内可执行约 10^8 次简单运算）。

举例： 题目给出 n ≤ 1000，时限 1 秒。

• O(n³) = 10^9 → 超时
• O(n²) = 10^6 → 可以
• 因此应选择 O(n²) 或更优的算法

✨ 算法的常见错误

1. 混淆时间复杂度和实际运行时间：O(n²) 并不意味着恰好执行 n² 次，它描述的是增长趋势。常数因子也会影响实际速度，但在复杂度分析中被忽略。
2. 只看循环层数来判断复杂度：两层循环不一定是 O(n²)。例如，内层循环的总执行次数可能是 O(n) 而非 O(n²)，需要具体分析。
3. 忽略空间复杂度：开了一个大小为 10^8 的数组，虽然时间可能没问题，但内存就超限了。int 类型的 10^8 个元素需要约 400MB 内存。
4. 忘记考虑输入输出的时间：大量数据的 cin/cout 可能很慢，竞赛中可以使用 ios::syncwithstdio(false) 和 cin.tie(0) 来加速。

三、课后练习

基础知识练习

• 算法概述 - 选择题