算法设计与分析：要点总结-1

算法概述

算法的5大特性

确定性:算法的每一步骤必须有明确的定义，无二义性。即在相同输入下，每次执行都应得到相同的结果。
能行性:算法的每一步都必须是可实现的，即在有限时间内能用有限资源完成。
输入：算法可以有零个或多个输入，输入是算法处理的初始数据。
输出：算法必须有一个或多个输出，输出是算法处理的结果。
有穷性/有限性：算法必须在执行有限步骤后终止，不能无限循环。

算法与计算过程的区别

计算过程可能无限执行（如操作系统），而算法必须是有穷的。

算法描述的主要语言

自然语言：直观但容易歧义。
伪代码：介于自然语言和编程语言之间，结构清晰，无语法限制。
流程图：图形化表示，直观展示控制流。
编程语言：直接实现，但需关注语法细节。

渐进表示

定义

O（大O符号，上界）： f(n)=O(g(n)) 表示存在常数 c>0 和 n0，使得对所有 n≥n0，有 f(n)≤c⋅g(n)。

表示算法的最坏情况时间复杂度。

Ω（Omega，下界）： f(n)=Ω(g(n)) 表示存在常数 c>0 和 n0，使得对所有 n≥n0，有 f(n)≥c⋅g(n)。

表示算法的最好情况时间复杂度。

Θ（Theta，紧确界）： f(n)=Θ(g(n)) 当且仅当 f(n)=O(g(n)) 且 f(n)=Ω(g(n))。

表示算法的平均情况时间复杂度。

多项式定理

若 f(n) 是 d 次多项式，则 f(n)=Θ(n**d)。

常见的多项式/指数限界函数

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

渐进符号O运算性质

传递性：若 f(n)=O(g(n)) 且 g(n)=O(h(n))，则 f(n)=O(h(n))。
加法规则：O(f(n))+O(g(n))=O(max⁡(f(n),g(n)))。
乘法规则：O(f(n))⋅O(g(n))=O(f(n)⋅g(n))。

重要例题

冒泡排序

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 示例
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))  # 输出: [11, 12, 22, 25, 34, 64, 90]

警察抓小偷

信息数字化。

竞赛预测

信息数字化。将逻辑问题转化为代码，遍历求解。

楼梯台阶问题

def climb_stairs(n):
    if n 
- **基准情形**：明确递归终止条件（如 n=0 或 n=1）。

- **递归调用**：将问题分解为更小的同类子问题。

- **正确性证明**：通常用数学归纳法验证。

### 循环与递归的比较

| 比较维度 | 循环（迭代） | 递归 |
| --- | --- | --- |
| 程序可读性 | 通常更直观，适合线性逻辑（如遍历数组）。 | 更符合数学思维，适合分治、树/图遍历等问题，但嵌套过深时难理解。 |
| 代码量 | 通常较短，尤其是简单循环（如 for、while）。 | 可能更简洁（如阶乘、斐波那契数列），但需要额外递归终止条件。 |
| 时间效率 | 无函数调用开销，执行更快（适合大规模数据）。 | 每次递归调用需保存栈帧，函数调用开销大，可能更慢。 |
| 占用空间 | 仅需固定内存（如几个变量），空间复杂度通常为 O(1)。 | 需保存每一层调用的栈帧，空间复杂度取决于递归深度（如 O(n) 或 O(log⁡n)），可能栈溢出。 |
| 适用范围 | 所有可迭代问题（如数组遍历、数值计算）。 | 适合分治（如归并排序）、回溯（如八皇后）、树/图遍历（如DFS）等递归定义的问题。 |
| 设计难度 | 较直观，适合顺序逻辑。 | 需找到子问题分解方式，设计递归终止条件，对思维抽象能力要求更高。 |

 一般的，理论上，循环（迭代）都可以改写成递归，反之不然。 

### 常用数据结构的比较

- **数组**：随机访问快，插入/删除慢。

- **链表**：插入/删除快，访问需遍历。

- **栈/队列**：特定顺序操作（LIFO/FIFO）。

- **哈希表**：快速查找，但需处理冲突。

### 重要例题

#### 欧几里得算法

```python
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# 示例
print(gcd(48, 18))  # 输出: 6

Hanoi塔

def hanoi(n, source, target, auxiliary):
    """
    汉诺塔递归解法
    :param n: 盘子数量
    :param source: 起始柱子（如 'A'）
    :param target: 目标柱子（如 'C'）
    :param auxiliary: 辅助柱子（如 'B'）
    """
    if n == 1:
        # 基准情形：只有一个盘子时，直接移动到目标柱子
        print(f"Move disk 1 from {source} to {target}")
    else:
        # 递归步骤：
        # 1. 将前 n-1 个盘子从 source 移到 auxiliary（借助 target）
        hanoi(n-1, source, auxiliary, target)
        
        # 2. 将第 n 个盘子（最大的）从 source 移到 target
        print(f"Move disk {n} from {source} to {target}")
        
        # 3. 将前 n-1 个盘子从 auxiliary 移到 target（借助 source）
        hanoi(n-1, auxiliary, target, source)

# 示例：移动 3 个盘子从 A 到 C，借助 B
hanoi(3, 'A', 'C', 'B')

整数的划分

def integer_partition(n, m):
    """
    计算将整数 n 划分为最大部分不超过 m 的划分数。
    :param n: 待划分的整数。
    :param m: 划分中允许的最大部分。
    """
    if n == 0:
        return 1  # 空划分算一种
    if m == 1:
        return 1  # 只能划分为 1+1+...+1
    if n 
- **初始化**：设定初始状态（如变量初值）。

- **迭代过程**：通过循环逐步更新状态。

- **终止条件**：达到目标时退出循环。

### 递推法vs倒推法

- **递推法**：从已知条件逐步推导到目标（如斐波那契数列）。

- **倒推法**：从目标反向推导初始条件（如猴子吃桃问题）。

### 重要例题

#### 兔子繁衍问题

```python
def fibonacci(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# 示例
print(fibonacci(6))  # 输出: 8（第6个月有8对兔子）

猴子吃桃问题

def peach_count(days):
    peaches = 1  # 最后一天剩1个
    for _ in range(days-1):
        peaches = (peaches + 1) * 2
    return peaches

# 示例
print(peach_count(5))  # 输出: 46（第1天有46个桃子）

杨辉三角形

递推关系：C(n,k)=C(n−1,k−1)+C(n−1,k)。

穿越沙漠问题（重点在于如何理解其思想）

核心思想：分段设立补给站，逆向计算资源消耗。

牛顿迭代法

求方程根：xn+1=xn−f(xn)/f′(xn)。

蛮力法

重要例题

百钱百鸡问题

def hundred_chickens():
    for x in range(0, 21):       # 公鸡最多20只
        for y in range(0, 34):    # 母鸡最多33只
            z = 100 - x - y
            if 5*x + 3*y + z/3 == 100:
                print(f"公鸡: {x}, 母鸡: {y}, 小鸡: {z}")

# 示例
hundred_chickens()  # 输出所有解

解数字迷（ABCAB X A = DDDDDD）

def solve_abcab():
    for a in range(1, 10):
        for b in range(10):
            for c in range(10):
                abcab = 10000*a + 1000*b + 100*c + 10*a + b
                d = abcab * a
                if len(str(d)) == 6 and len(set(str(d))) == 1:
                    print(f"ABCAB = {abcab}, A = {a}, D = {d}")

# 示例
solve_abcab()  # 输出: ABCAB = 37037, A = 3, D = 111111

狱吏问题（蛮力->数学技巧->深入挖掘数学规律）

def prison_doors(n):
    doors = [False] * n  # False表示门关闭
    for i in range(1, n+1):
        for j in range(i-1, n, i):
            doors[j] = not doors[j]
    return [i+1 for i, door in enumerate(doors) if door]

# 示例
print(prison_doors(10))  # 输出: [1, 4, 9]（完全平方数编号的门开着）