算法基础 原创

一、算法的基本概念

1.1 定义

• 算法是为了解决特定问题而规定的一个有限长的操作序列。它是一系列清晰、准确的指令。

1.2 特性

• 算法有五个重要特性，分别为：
  1. 有穷性：算法必须在执行之后结束，且。
  2. 确定性：算法中的每一条指令必须有，不会产生二义性。在任何条件下，对于。
  3. 可行性：算法中描述的操作都是可以通过已经实现的来实现的。
  4. 输入：一个算法有输入。
  5. 输出：一个算法有输出。输出是与输入有某种特定关系的量。

1.3 算法 & 程序

一般来说一个简单的程序可以理解成： ，算法解决"如何做"，数据结构解决"数据如何组织"

• 算法：是一种思想，不拘泥于形式，可以用自然语言、伪代码、流程图描述。。
• 程序：是某种程序设计语言对算法的。可以是（如操作系统，一直在运行）。

二、算法的评价标准

评价一个算法的好坏，核心是分析其。效率主要通过和来衡量。

2.1

• 定义：定性描述算法（不是实际时间，）随问题规模 n 增长的变化趋势。

• 表示法：，它表示的是算法运行时间的（最坏情况下的趋势）。

• 计算方法：

  1. 找出算法中所有的执行次数 T(n) 关于问题规模 n 的函数。
  2. 只保留函数的。
  3. 忽略最高阶项的。

• 常见的复杂度排序（）：

复杂度	名称	示例
O(1)	常数阶	访问数组元素、表达式计算
O(log n)	对数阶	二分查找
O(n)	线性阶	遍历数组、查找最大值
O(n log n)	线性对数阶	快速排序、归并排序（高效排序算法）
O(n²)	平方阶	冒泡排序、选择排序（简单排序算法）
O(n³)	立方阶	Floyd算法、矩阵乘法
O(2ⁿ)	指数阶	汉诺塔、穷举搜索（不可接受）
O(n!)	阶乘阶	旅行商问题（不可接受）

2.2

• 定义：定性描述算法在运行过程中大小随问题规模 n 增长的变化趋势。
• 组成：主要包括：
  • 指令空间：存储。
  • 数据空间：存储数据。
  • 环境栈空间：所需的信息（如返回地址、参数等）。
  • （通常我们主要关注）
• 表示与计算：同样使用，计算方法与。
• 递归调用时：函数递归调用时记作 ->

2.2.3 复杂度分析示例

// 示例1：时间复杂度 O(n)，空间复杂度 O(1)
int sum(int n) {
    int s = 0;           // 1次
    for (int i=1; i<=n; i++) { // i<=n 执行 n+1 次，i++ 执行 n 次
        s = s + i;       // 执行 n 次
    }
    return s;            // 1次
}
// T(n) = 1 + (n+1) + n + n + 1 = 3n + 3 --> 使用 O 的表示方法，舍去常量和系数 --> O(n)
// S(n) = 只用了常数个变量 (s, i, n) -> O(1)

// 示例2：时间复杂度 O(n²)，空间复杂度 O(1)
void bubbleSort(int a[], int n) {
    for (int i=0; i<n-1; i++) {        // 循环 n-1 次
        for (int j=0; j<n-1-i; j++) {  // 循环 ~n 次
            if (a[j] > a[j+1]) {       // 基本操作
                swap(a[j], a[j+1]);    // 基本操作
            }
        }
    }
}
// 内层循环次数为 (n-1) + (n-2) + ... + 1 = n(n-1)/2 -> O(n²)

// 示例3：递归算法的空间复杂度 O(n)
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n-1);
}
// 每次递归调用都会在栈中分配空间存储参数和返回地址。
// 递归深度为 n，所以空间复杂度为 O(n)。

四、算法设计方法概述

1. 递归与分治：将求解（如：快速排序、归并排序）。
2. 贪心算法：每一步都做出的选择，希望导致全局最优（如：霍夫曼编码、最小生成树的Prim和Kruskal算法）。不一定能得到全局最优解。
3. 动态规划：将问题分解为，通过来避免重复计算（如：Fibonacci数列、背包问题、Floyd算法）。
4. 回溯法：一种选优搜索法，按选优条件向前搜索，达（如：N皇后问题）。
5. 分支限界法：类似回溯法，但按广度优先策略遍历解空间树。

五、小结

1. 必考内容：时间/空间复杂度的。
2. 核心技能：一定要会。
3. 下午题关联：在解答下午的算法填空题时，心中要对所填代码的复杂度有一个预估，这有助于理解算法的效率和正确性。
4. 记忆口诀：常见复杂度的大小关系要牢记：。