算法概述

用计算机求解问题的步骤：

1. 分析问题
2. 建立数学模型
3. 算法设计与选择
4. 算法表示
5. 算法分析
6. 算法实现

算法三要素：

1. 操作
2. 控制结构
3. 数据结构

算法的性质：

1. 有穷性：算法必须在执行有限步骤后终止，不能无限循环，每一步骤也需在有限时间内完成
2. 确定性：算法的每条指令必须有明确的含义，无二义性，相同的输入必须产生相同的执行路径和结果
3. 输入：算法有 0 个或多个输入，作为算法处理的初始数据
4. 输出：算法至少有一个输出
5. 可行性：算法中的每一步必须可被实现，且能用基本运算组合完成
6. 鲁棒性：对非法输入能做出合理处理（如返回错误提示）。
7. 效率：通过时间复杂度和空间复杂度衡量性能。

自然语言表示算法的优缺点：

优点：

• 直观易懂
• 灵活性高
• 快速表达思想
• 无语法限制

缺点：

• 歧义性
• 缺乏结构性
• 无法直接执行
• 效率描述困难
• 验证难度大

衡量一个算法优劣的指标：算法复杂度和时间复杂度

算法复杂度：“循环轮数”

1. 插入排序（Insertion Sort）

思想：将未排序部分的元素逐个插入到已排序部分的正确位置。
特点：

• 时间复杂度：最好 O(n)（已有序），最坏 O(n²)
• 空间复杂度：O(1)（原地排序）
• 稳定排序

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr
​

2. 选择排序（Selection Sort）

思想：每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。
特点：

• 时间复杂度：始终 O(n²)
• 空间复杂度：O(1)
• 不稳定排序（交换可能破坏顺序）

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]  # 交换
    return arr
​

3. 冒泡排序（Bubble Sort）

思想：重复比较相邻元素，将较大的元素逐步“冒泡”到右侧。
特点：

• 时间复杂度：最好 O(n)（已有序），最坏 O(n²)
• 空间复杂度：O(1)
• 稳定排序

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False  # 优化：若未发生交换，提前退出
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr
​

4. 快速排序

快速排序是一种分治（Divide and Conquer） 算法，核心思想是：

1. 选择一个基准值（pivot） （通常为数组的第一个或最后一个元素）。
2. 分区（Partition） ：将数组分为两部分，左边小于基准值，右边大于基准值。
3. 递归排序左右子数组。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]  # 选择最后一个元素作为基准
    left = [x for x in arr[:-1] if x <= pivot]  # 小于等于基准的部分
    right = [x for x in arr[:-1] if x > pivot]  # 大于基准的部分
    return quick_sort(left) + [pivot] + quick_sort(right)  # 递归拼接
​

缺点：

• 每次递归创建新列表，空间复杂度高（O(n)） 。
• 对已排序数组表现差（时间复杂度退化为 O(n²)）。

递归：自己调用自己

特点：

1. 简洁、易理解
2. 效率低，消耗内存高

汉诺塔

def hanoi(n,a,b,c):
    if n > 0:
        hanoi(n-1,a,c,b)
        print("mooving from %s to %s"%(a,c))
        hanoi(n-1,b,a,c)
hanoi(3,'A','B','C')
​

0-1 背包问题

def knapsack_01(values, weights, capacity):
    n = len(values)
    # 初始化DP表，(n+1) x (capacity+1)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                # 选择当前物品或不选择，取最大值
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                # 不能选择当前物品
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]
​