【笔记】算法分析与设计

《算法分析与设计》课程复习笔记

算法分析基础

渐进分析

常见的大O运行时间

排序算法

插入排序

  • 时间复杂度:$O(n^2)$

  • 空间复杂度:$O(n)$

  • 示例代码(Python):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def insert_sort(arr):
    for i in range(1, len(arr)):
    curr = arr[i]
    j = i - 1
    while j > 0 and arr[j] > curr:
    arr[j+1] = arr[j]
    j -= 1
    arr[j+1] = curr
    return arr
  • 图示

归并排序

  • 时间复杂度:$O(nlogn)$
  • 空间复杂度:$O(n)$
  • 算法概况

    • 第一步:将序列利用二分法分成两个子序列
    • 第二步:递归第一步,直到序列只有一个元素
    • 第三步:将递归返回的两个子序列(有序),进行有序合并,形成一个新的子序列
    • 第四步:递归返回,逐渐合并为有序原序列
  • 示例代码(Python):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
    if left[i] <= right[j]:
    result.append(left[i])
    i += 1
    else:
    result.append(right[j])
    j += 1
    result += left[i:]
    result += right[j:]
    return result

    def merge_sort(arr):
    if len(arr) <= 1:
    return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
  • 图示

快速排序

  • 时间复杂度
    • 最优和平均:$O(nlogn)$
    • 最差:$O(n^2)$
  • 算法概括:

    • 第一步:选择一个基准数(pivot),设置两个指针i j ,分别以头和尾作为起点,j先向左移动直到找到一个比基准数小的然后停止,i向右移动直到找到一个比基准数大的停止,两个数交换位置,直到i碰到j,完成一个基准数的定位,将该位置的数与基准数交换,完成第一次排序。
    • 第二步:以上次的基准数为分界点,分成左右两个子序列(partitioning),分别对左右两个子序列进行第一步。
    • 第三步:循环第二步,直到排序完成。
  • 示例代码(Python)

    1
    2
    3
    4
    5
    6
    7
    8
    def quick_sort(arr):
    if len(arr) < 2: # 基线条件:为空或只包含一个元素的数组是有序的
    return arr
    else:
    pivot = arr[0] # 递归条件
    less = [i for i in arr[1:] if i <= pivot] # 由所有小于基准值的元素构成的子数组
    greater = [i for i in arr[i:] if i > pivot] # 由所有大于基准值的元素构成的子数组
    return quick_sort(less) + [pivot] + quick_sort(greater)

动态规划

钢条切割问题

  • 问题描述: 给定一段长度为$n$英寸的钢条和一个价格表$p_i(i = 1, 2, …, n)$,求切割钢条方案,使得销售收益$r_n$最大。

  • 数学表示:
    $$
    r_n = max(p_n, r_1 + r_{n-1}, r_2 + r_{n-2}, …, r_{n-1} + r_1)
    $$
    简化版本
    $$
    r_n = max(p_i + r_{n-i}) ~(1\le i \le n)
    $$

  • 示例代码:

    • 自底向上实现

      1
      2
      3
      4
      5
      6
      7
      8
      9
      def cut_rod(p):  # p为钢条价格表
      n = len(p) # n为钢条长度
      for i in range(n):
      q = -10 # 临时变量
      for j in range(i + 1):
      if q < p[i] + r[j-i]:
      q = p[i] + r[j-i]
      s[j] = i # s表示最优解对应的第一段钢条的切割长度
      r[j] = q # r表示长度为i的钢条最大收益

0-1背包问题

  • 问题描述: 有 $N$ 件物品和一个容量为$V$ 的背包。第 $i$ 件物品的费用是 $w_i$,价值是 $p_i$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

  • 递归数学表达式:

  • 状态转移方程:

    1
    f[i][v] = max{f[i-1][v], f[i-1][v-w[i]]+p[i]}
  • 核心代码:

    1
    2
    3
    for i in range(n):
    for v in range(w[i], V):
    f[i][v] = max(f[i-1][v], f[i-1][v-w[i]]+p[i])
  • 时间复杂度: $O(VN)$

  • 空间复杂度: $O(VN)$

矩阵链相乘

  • 问题描述: 给定$n$个矩阵构成的一个链$(A_1A_2A_3……A_n)$ ,其中$i=1,2,……n$, 矩阵 $A_i$ 的维数为$p_{i-1}p_i$,对于乘积$A_1A_2A_3……A_n$以一种最小化标量乘法次数的方式进行加括号。

  • 递归数学表达式:

  • 状态转移方程:

    1
    m[i, j] = min(m[i, k] + m[k+1, j] + p(i-1)p(k)p(j)) i <= k < j

最长公共子序列(LCS)

  • 递归数学表达式:

贪心算法

贪心策略证明

  1. 若运用贪心策略,将在子问题A中,选择a作为局部最优解
  2. 即是证明在不采取贪心策略下,原问题的最优解中,也包含a
  3. 假设,此时子问题A中没有选择a,证子问题B(递归中与合并后)中的选择一定包含a
  4. 此时,可以使用最简单的证法,也就是动态规划的自底向上递归。由于a在切分扫描中,一定被选中
  5. 由4可得3,也就是得到了“贪心策略选择的局部最优解,一定包含在全局最优解之中”

答题套路

证明:

  1. 假设$w_1, w_2, …w_n$按升序排列,$s$为一个全局最优解,包括$w_{i1}, w_{i_2}, … w_{in}$,同样按升序排列
  2. 若$w_1 = w_{i1}$则贪心策略显然成立
  3. 若$w_1 \neq w_{i1}$
    • 设$s’ = {s - w_{i1}} \cup {w_1} ~ (w_1 \le w_{i1}) $
    • $s’$的价值等于$s$的价值
    • $s’$也一定为全局最优解$w_1 \in s$

所以得证贪心策略成立。

网络流

常见定理证明

  • $f(X, X) = 0$

    证明:

  • $f(X, Y) = -f(Y, X)$

    证明: