Lazy loaded image
学习笔记
🧠算法设计与分析
字数 1605阅读时长≈ 5 分钟
2026-4-16
2026-4-16
type
Post
status
Published
date
Apr 16, 2026
slug
algorithm-design-and-analysis
summary
算法设计笔记
tags
C++
C
Python
算法
category
学习笔记
icon
password
By BarryZed

算法概述

性质：
  • 有穷性：一个算法必须总是在执行有穷步骤之后结束，且每一步都在有穷时间内完成。
  • 确定性：算法中每一条指令必须有确切的含义。不存在二义性。即对于相同的输入只能得出相同的输出。
  • 可行性：一个算法是可行的。即算法描述的操作都是可以通过已经实现基本运算，执行有限次来实现的
  • 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
  • 输出：一个算法有一个或多个输出，这些输出同输入之间有着某些特定的关系。
分析复杂度：
  • 渐进分析：只要最高次项，忽略系数与其他项
    • 渐进上界里c是常数，只要够大就行，满足条件再大也可以
      • 迭代法示例
      第1步：写出原始式
      T(n) = T(n-1) + c     （c 是常数）
      第2步：开始迭代展开（写几层看模式）
      T(n)   = T(n-1) + c
      = [T(n-2) + c] + c = T(n-2) + 2c
      = [T(n-3) + c] + 2c = T(n-3) + 3c
      = [T(n-4) + c] + 3c = T(n-4) + 4c
      ……
      第3步：写出通用形式（第 i 层）
      T(n) = T(n - i) + i·c
      第4步：确定展开到什么时候（找 k）
      我们一直展开到子问题规模变成基例，即 n - i ≤ 1
      → i = n - 1   （当 i = n-1 时，n - (n-1) = 1）
      第5步：代入 k 并化简（重点讲清楚）
      把 i = n-1 代入通用形式：
      T(n) = T(n - (n-1)) + (n-1)·c
      = T(1) + (n-1)·c
      因为 T(1) = Θ(1)，(n-1)·c 是线性项，
      所以：
      T(n) = Θ(1) + Θ(n-1) = Θ(n)
      ——Grok
      Master Theory
      notion image
       

递归与分治策略

分治法的要求：
  1. 子问题与原问题性质完全相同
  1. 子问题之间相互独立，可分别求解
  1. 最小子问题可以直接求解
n位大整数乘法

动态规划

矩阵连乘问题

变量名
m[i][j] ：到连乘的最少乘法次数
p[i] ：存的是维数，的维数是p[i] x p[i+1]
s[i][j]：i,j之间最佳断点
notion image
notion image
s[][]存放的是i,j之间最佳断点，就是上面转移方程中m[i][j] 取到时k 的值，加括号：
  • s[1][1] （i==k 没有意义直接跳过）
  • s[1][2] = 1 ：1，2之间在1后加括号（即1自己加括号括起自己没有意义）
…
  • s[1][4] = 3 ：1，4之间在3后加括号（即1、2、3括起来，4、5、6括起来）
  • s[1][5] = 3 ：1，5之间在3后加括号（即不变）
…
  • s[2][4] = 3 ：2，4之间在3后加括号（即2、3括起来，4单独不用管）
…
  • s[4][6] = 5 ：4，6之间在5后加括号（即4、5括起来，6单独不用管）
最后答案为(1 (2 3)) ((4 5) 6)

最长公共子序列（LCS, Longest Common Subsequence）问题

变量名
X, Y ：原序列
Z ：LCS
c[i][j] ：序列和的最长公共子序列的长度
LU, L, U : Left-up, Left, Up
rec[i][j] ：记录子问题最优解的来源内容LU/L/U
如果c[i][j] 取了c[i-1][j] 说明行号更小，往上走了，所以rec[i][j] = U ，另一个取L 同样道理
c[i-1][j] 与c[i][j-1] 相等时，优先取U
通过rec 写出LCS：从右下角开始：LU就取字符并斜走，U向上，L向左，最后逆序输出

最大子段和（Maximum Subarray Sum）问题

变量名
：以开头的最大子序列
rec[i]：以 为起点的最优连续子数组的结束位置
rec[3]=6：为
当，则有,反之，当，则有
由于要知道的值，所以要从后开始算
例子：（本表格白字部分是填的，从后往前，每一列先再rec）
ㅤ
i
1
2
3
4
5
6
7
8
9
10
11
12
X
ㅤ
1
-2
4
5
-2
8
3
-2
6
3
7
-1
D
ㅤ
31
30
32
28
23
25
17
14
16
10
7
-1
rec
ㅤ
11
11
11
11
11
11
11
11
11
11
11
12
得出最大子段和为，rec[3] = 11 ，所以是~

0-1背包问题

变量
v[i] ：第i 件物品的价值
w[i] ：第i 件物品的重量
x[i] ：0为不拿，1为拿
m[i][j]=前i件物品，在容量j下的最大价值
如果 m[i][j] == m[i-1][j]⇒ 没选第 i 个
如果 m[i][j] > m[i-1][j]⇒ 选了第i 个
——ChatGPT
例子
i(w/v) \ j
0
1
2
3
4
5
6
7
8
9
10
0
0
0
0
0
0
0
0
0
0
0
0
1(2/6)
0
0
6
6
6
6
6
6
6
6
6
2(2/3)
0
0
6
6
9
9
9
9
9
9
9
3(6/5)
0
0
6
6
9
9
9
9
11
11
14
4(5/4)
0
0
6
6
9
9
9
10
11
13
14
5(4/6)
0
0
6
6
9
9
12
12
15
15
15
从m[n][W]倒推
从m[5][10] = 15 开始
🔹 第一步：i=5（物品 e），j=10
对比：
  • m[5][10] = 15
  • m[4][10] = 14
👉 不一样 ⇒ 选了 e
背包容量减少：
👉 j = 10 - 4 = 6
🔹 第二步：i=4（物品 d），j=6
对比：
  • m[4][6] = 9
  • m[3][6] = 9
👉 一样 ⇒ 没选 d
👉 j 不变 = 6
🔹 第三步：i=3（物品 c），j=6
对比：
  • m[3][6] = 9
  • m[2][6] = 9
👉 一样 ⇒ 没选 c
👉 j 不变 = 6
🔹 第四步：i=2（物品 b），j=6
对比：
  • m[2][6] = 9
  • m[1][6] = 6
👉 不一样 ⇒ 选了 b
👉 j = 6 - 2 = 4
🔹 第五步：i=1（物品 a），j=4
对比：
  • m[1][4] = 6
  • m[0][4] = 0
👉 不一样 ⇒ 选了 a
👉 j = 4 - 2 = 2（结束其实已经够了）
选了abe
上一篇
“三下乡”
下一篇
应用统计学
  • 作者:BarryZed
  • 链接:
  • 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
评论
Loading...
目录