首页课程学习算法设计与分析

# 几种算法基本理解

# 贪心算法

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

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

在贪心策略下

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

你的选择就是 [1,3]

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

# 穷举法

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

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

比如x1,x2,x3,x4x_1,x_2,x_3,x_4，4（nn）个变量都是自然数，已知其和为 5（mm），求总共多少种情况？

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

1…1⏟x1个  0  1…1⏟x2个  0  1…1⏟x3个  0  1…1⏟x4个\underbrace{1\dots1}_{x_1个}\;0\;\underbrace{1\dots1}_{x_2个}\;0\;\underbrace{1\dots1}_{x_3个}\;0\;\underbrace{1\dots1}_{x_4个}

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

# 排序算法

  • 插入排序

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

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


  • 冒泡排序

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

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


  • 选择排序

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

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


  • 快速排序

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

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

    排序不稳定，会乱交换


  • 归并

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

    排序稳定，很少有交换

# 主定理

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

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

W(n)=nlogba,  ϵ>0T(n)={Θ(W(n))f(n)=O(nlogba−ϵ)Θ(W(n)logn)f(n)=Θ(nlogba)Θ(f(n))f(n)=Ω(nlogba+ϵ),  ∃ n,c<1,  af(n/b)≤cf(n)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)W(n) 和f(n)f(n)，哪个数量级大取哪个
  • 若连两者相等，则多乘一个lognlogn
  • 对于f(n)f(n) 较大的情况，则要满足额外不等式条件

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

# 符号整理

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

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

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

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