# 几种算法基本理解

# 贪心算法

贪心，即选择当下的局部最优解

比如 0-1 背包问题，负重 6 的背包，4 个货，按单位重量价值从高到低给货物编号 [1,2,3,4] ，

在贪心策略下

• 你先选了单位重量价值最高的货物 1
• 剩余背包负重只够你选货物 3 的，于是再选 3
• 剩余背包负重不能再装任何货物了

你的选择就是 [1,3]

然而局部最优不一定是整体最优，很可能最优解是 [2,3]

# 穷举法

暴力枚举：我的超级智慧告诉我要使用我的超级力量了

再复习时，我发现一个有意思的问题 —— 怎么确定全体情况的数量？换句话说，我要枚举多少情况才算枚举干净了没遗漏？

比如$x_1,x_2,x_3,x_4$，4（$n$）个变量都是自然数，已知其和为 5（$m$），求总共多少种情况？

这时可以把 “和为 5” 看作五个 1，然后用 0 来间隔，每个情况就是一个 01 序列，对应序列即：

$$\underbrace{1\dots1}_{x_1个}\;0\;\underbrace{1\dots1}_{x_2个}\;0\;\underbrace{1\dots1}_{x_3个}\;0\;\underbrace{1\dots1}_{x_4个}$$

此时求序列有多少，即 “排位子” 问题，$m$ = 变量和 = 1 的个数，$n$ = 变量个数 = 0 的个数 + 1，一共 m+n-1 个座位，选 m 个位子放 1，结果即$C\binom{m+n-1}{m}$

# 排序算法

• 插入排序

  数列前面的是排好的，画黄条；后面没排好，画白条；取没排好的第一个数，插入到黄条中正确的位置；重复，黄条渐长，白条渐短，最后都是排好的黄条

  排序稳定，选中$x$，按从后往前的顺序，找到黄条中小于等于$x$ 的数$t$，把$x$ 插在$t$ 后面

  
  

• 冒泡排序

  数列前面没排好，画白条，后面排好的画黄条；
  每巡回一次，就是从左往右不断两两比较，进行一些交换，把大的数换在右边；
  于是白条中最大的数像泡泡一样浮出来，进入右边黄条；重复

  排序稳定，比较是比较相邻的两个元素，交换也是发生在这两个元素之间。两个元素相等，你总不会无聊地把它俩交换一下吧

  
  

• 选择排序

  数列前面的是排好的，画黄条；后面没排好，画白条；
  选择排序本质是，给每个位置选择白条元素中最小的。比如给第一个位置选择最小的，给第二个位置选择剩余元素里面第二小的，依次类推。

  排序不稳定，例如序列 “5 (1) 8,5 (2),2,9”，5 (1) 会和 2 交换，破坏稳定性。

  
  

• 快速排序

  本质就是选择一个数$x$，一轮操作下来，比$x$ 小的放到其左边，比$x$ 大的放到其右边，然后对左右两堆继续操作……

  一轮 partition：
  数列$x_0,x_1,\dots,x_{n-1}$ 中随机选一个数$t$ 作为 pivot，将 pivot 和$x_0$ 交换位置
  左指针$l=0$，右指针$r=n-1$
  若$x_r>t,\,r=r-1$；直到$x_r<t$，将$x_r$ 换到指针 l 的位置，$l=l+1$
  若$x_l\le t,\,l=l+1$；直到$x_l>t$，将$x_l$ 换到指针 r 的位置，$r=r-1$
  重复，直到 l=r，令此时指针位置的值为 t
  对 t 左右两堆分别 partition，直到完成

  排序不稳定，会乱交换

  
  

• 归并

  比较容易理解，代码难写，思路就是先两两排序，再把临近的两个小堆合并排序，越滚越大，最后合并两个大数列得到最终的原完整数列

  排序稳定，很少有交换

# 主定理

对于递推回归式，求其时间复杂度用。

对于$T(n)=aT(n/b)+f(n)$，$a\geq1,\;b>1$，则：

$$W(n)=n^{log_ba},\;\epsilon>0\\ T(n)=\begin{cases} \Theta(W(n))&f(n)=O(n^{log_ba-\epsilon})\\ \Theta(W(n)logn)&f(n)=\Theta(n^{log_ba})\\ \Theta(f(n))&f(n)=\Omega(n^{log_ba+\epsilon}),\;\exist\,n,c<1,\;af(n/b)\leq cf(n)\\ \end{cases}$$

解释一下，就是

• 对于$W(n)$ 和$f(n)$，哪个数量级大取哪个
• 若连两者相等，则多乘一个$logn$
• 对于$f(n)$ 较大的情况，则要满足额外不等式条件

Tips：在数量级计算上，对任意$\epsilon>0$，$log(n)<n^\epsilon$

# 符号整理

大$O$ 符号，$f(n)=O(g(n))$，f 不高于 g 的阶，$f\leq g$

大$\Omega$ 符号，$f(n)=\Omega(g(n))$，f 不低于 g 的阶，$f\geq g$

小$o$ 符号，$f(n)=o(g(n))$，f 低于 g 的阶，$f< g$

小$\omega$ 符号，$f(n)=\omega(g(n))$，f 高于 g 的阶，$f> g$