数据结构 01 绪论 + 性能测度

图灵机模型（TM）

每个转化函数具有五个参数
状态，当前正对的字符；在当前单元填入或者修改的新字符，向左或向右移动，更改状态（ ← → h ）

实例:

复位读写头的目的是为了规范性，做为一个固定的算法可以使用

RAM 模型

Random Access Machine

依赖这两种模型可以不用考虑运行环境

能够客观度量算法性能

实例:

大 O 记号

需执行的基本操作次数：T（n）
需占用的存储单元数: S（n）

考虑算法时不关心细微的变化趋势

给出了时间复杂度的上界

渐近分析：其他记号

欧米噶记号（给出了时间复杂度的下界） 和 谁他记号（两者均衡下来的度量记号）
因为更多的时候都是要从悲观的角度分析，所以使用大 O 记号多一些

大 O 记号的多种常见复杂度

• $O(1)$: 常数运算 $2020^{2020}=O(1)$
  不含转向（循环调用递归等），必顺序执行，即是 O（1）
• $O(log^cn)$:
  对数或者对数多项式复杂度
  这类算法非常有效，复杂度无限接近于常数，低于任何一个多项式复杂度
  
• 多项式复杂度
  凡是多项式复杂度，即可视作可解
  
• 指数复杂度（难解）

2-Subset

指数复杂度和多项式复杂度算法不能轻易转化的实例

S 包含 N 个正整数，$\sum S=2m$
S 是否有子集 T，满足$\sum T=m$?

级数

一般不会太用到级数的相关内容，下面这些熟记即可
具体数学中会给出更多实例

循环 vs 级数

实例

考虑空间复杂度时不包含输入数据的空间

考虑递归算法 想清楚递归基的运算元素数量（相当于考虑几次 for 循环）

动态规划

3.3.1--3.3.10

递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。

放 gitbook 用来参考
https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie

斐波那契

leetcode (opens new window)

• 斐波那契数列递归实现

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

因为存在多个重复的子元素，复杂度为 $O({\frac{1+\sqrt{5}}{n}}^{2})=O(2^n)$
空间复杂度为 O（n），超级大

明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。

int fib(int N) {
    if (N < 1) return 0;
    // 备忘录全初始化为 0
    vector<int> memo(N + 1, 0);
    // 进行带备忘录的递归
    return helper(memo, N);
}
int helper(vector<int>& memo, int n) {
    // base case 
    if (n == 1 || n == 2) return 1;
    // 已经计算过
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}

实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。
子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f (1), f (2), f (3) ... f (20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O (n)。

解决一个子问题的时间，同上，没有什么循环，时间为 O (1)。
所以，本算法的时间复杂度是 O (n)。比起暴力算法，是降维打击。
至此，带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和迭代的动态规划已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。

啥叫「自顶向下」？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f (20)，向下逐渐分解规模，直到 f (1) 和 f (2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。
啥叫「自底向上」？反过来，我们直接从最底下，最简单，问题规模最小的 f (1) 和 f (2) 开始往上推，直到推到我们想要的答案 f (20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

• dp 数组的迭代解法

有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算岂不美哉！

int fib(int N) {
    vector<int> dp(N + 1, 0);
    // base case
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= N; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[N];
}

当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O (1):

int fib(int n) {
    if (n == 2 || n == 1) 
        return 1;
    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

最大公共子序列

子序列类型问题 (opens new window)

DP - 斐波那契
DP - 最长公共子序列

< 更多相关见 动态规划 (opens new window)