『算法』general

• 1. 算法
• 2. 可以解决哪些类型的问题
• 3. 算法分析
• 4. 算法设计
  
• 5. 递归式
  
  • 5.1. 代换法
    
  • 5.2. 递归树
  • 5.3. 主方法 (master method)
    
    • 5.3.1. 记忆
    • 5.3.2. 证明
      
• 6. 随机算法
  
  • 6.1. 随机排列数组 (shuffle)
    
• 7. 组合方程的近似算法
• 8. 概率分析与指示器变量例子
  

1. 算法

定义良好的计算过程, 取输入, 并产生输出. 即算法是一系列的计算步骤, 将输入数据转化为输出结果

2. 可以解决哪些类型的问题

• 大数据的存储, 以及开发出进行这方面数据分析的工具
• 网络数据的传输, 寻路, 搜索
• 电子商务密码, (数值算法, 数论)
• 资源分配, 最大效益
• …

3. 算法分析

衡量算法的优劣

• ο,O,Ω,Θ$o,O,\mathrm{\Omega },\mathrm{\Theta }$
• 最坏情况, 平均情况
• 增长的量级 O(1),O(logn),O(n),O(nk),O(an)$O(1),O(logn),O(n),O(n^k),O(a^n)$

4. 算法设计

4.1. 分治 (divide and conquer)

结构上是递归的,
步骤: 分解, 解决, 合并
eg 快排, 归并排序

5. 递归式

T(n)=aT(nb)+f(n)$T(n)=aT(\frac{n}{b})+f(n)$

5.1. 代换法

5.1.1. 步骤

• 猜测解的形式
• 用数学归纳法找出常数
  

5.1.2. 例子

T(n)=2T(n2)+n$T(n)=2T(\frac{n}{2})+n$
猜测 T(n)=O(nlogn)$T(n)=O(nlogn)$
证明 T(n)⩽cnlogn$T(n)⩽cnlogn$
归纳奠基 n=2,3
归纳假设 T(n2)⩽cn2$T(\frac{n}{2})⩽\frac{cn}{2}$
递归

T(n)⩽2cn2log(n2)+n⩽cnlog(n2)+n=cnlogn=cnlog2+n⩽cnlogn$$T(n)⩽2c\frac{n}{2}log(\frac{n}{2})+n⩽cnlog(\frac{n}{2})+n=cnlogn=cnlog2+n⩽cnlogn$$

5.1.3. 放缩

对于 T(n)=2T(cn2)+1$T(n)=2T(\frac{cn}{2})+1$
如果 直接猜测 T(n)=O(n)$T(n)=O(n)$ 不能证明,
而且不要猜测更高的界 O(n2)$O(n^2)$
可以放缩为 n-b

5.1.4. 改变变量

对于 T(n)=2T(n−−√)+logn$T(n)=2T(\sqrt{n})+logn$
可以 令 m = logn, 得到
T(2m)=2T(mm2)+m$T(2^m)=2T(m^{\frac{m}{2}})+m$
令 S(m)=T(2m)$S(m)=T(2^m)$
得到 S(m)=2S(m2)+m$S(m)=2S(\frac{m}{2})+m$

5.2. 递归树

例如 T(n)=3T(n4)+cn2$T(n)=3T(\frac{n}{4})+c{n}^2$
不妨假设 n 为 4 的幂, 则有如下递归树

每个结点是代价, 将每层加起来即可

5.3. 主方法 (master method)

对于 T(n)=aT(nb)+f(n)$T(n)=aT(\frac{n}{b})+f(n)$

T(n)=⎧⎩⎨⎪⎪⎪⎪⎪⎪Θ(nlogba),f(n)=O(nlogba−ϵ)Θ(nlogbalogn),f(n)=Θ(nlogba)Θ(f(n)),f(n)=Omega(nlogba+ϵ),且对常数c<1,任意大的 n, 有 af(nb)⩽cf(n)unknown,others$$T(n)=\{\begin{array}{l}\mathrm{\Theta }(n^{lo{g}_{b}a}),f(n)=O(n^{lo{g}_{b}a-ϵ})\\ \mathrm{\Theta }(n^{lo{g}_{b}a}logn),f(n)=\mathrm{\Theta }(n^{lo{g}_{b}a})\\ \mathrm{\Theta }(f(n)),f(n)=Omega(n^{lo{g}_{b}a+ϵ}),\text{且对常数}c<1,\text{任意大的 n, 有}af(\frac{n}{b})⩽cf(n)\\ unknown,others\end{array}$$

5.3.1. 记忆

直观上, 比较 nlogba$n^{lo{g}_{b}a}$ 和 f(n)$f(n)$, 谁大就是谁,
这里的大是多项式上的比较, 即比较次数, 而不是渐近上的
比如 n$n$ 与 nlogn$nlogn$ 渐近上后者大, 但多项式上是不能比较的

5.3.2. 证明

5.3.2.1. 证明当 n 为 b 的正合幂时成立

• 用递归树可以得到 总代价为 ∑logbn−1j=0ajf(nbj)$\sum _{j=0}^{lo{g}_{b}n-1}{a}^{j}f(\frac{n}{b^j})$
• 决定上式的渐近界
• 结合前两点

5.3.2.2. 分析扩展至所有正整数 n 都成立

主要是应用数学技巧来解决 floor, ceiling 函数的处理问题

6. 随机算法

6.1. 随机排列数组 (shuffle)

6.1.1. PERMUTE-BY-SORTING

给出初始数组, eg A={1,2,3}, 选择随机的优先级 P={16,4,10}
则得出 B={2,3,1}, 因为第二个 (2) 优先级最小, 为 4, 接着第三个, 最后第 1 个.
优先级数组的产生, 一般在 RANDOM(1,n^3), 这样优先级各不相同的概率至少为 1-1/n

由于要排序优先级数组, 所以时间复杂度 O(nlogn)$O(nlogn)$

如果优先级唯一, 则此算法可以 shuffle 数组
应证明 同样排列的概率是 1n!$\frac{1}{n!}$

6.1.2. RANDOMIZE-IN-PLACE

# arr: array to be shuffled
n = len(arr)
for i in range(n):
    swap(arr[i],arr[random(i,n-1)])

时间复杂度 O(n)$O(n)$
证明
定义循环不变式: 对每个可能的 Ai−1n$A_n^{i-1}$ 排列, 其在 arr[1..i-1] 中的概率为 1Ai−1n$\frac{1}{A_n^{i-1}}$
初始化: i=1 成立
保持 : 假设 在第 i-1 次迭代之前, 成立, 证明在第 i 次迭代之后, 仍然成立,
终止: 在 结束后, i=n+1, 得到 概率为 1n!$\frac{1}{n!}$

7. 组合方程的近似算法

• Stiring ‘s approximation: n!≈2πn−−−√(ne)n$n!\approx \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n$
• 对于 Cxn=a$C_n^x=a$, 有 x=ln2an$x=\frac{l{n}^{2}a}{n}$
• 对于 Cnx=a$C_x^n=a$, 有 x=(a∗n!)1n+n2$x=(a\ast n!{)}^{\frac{1}{n}}+\frac{n}{2}$

8. 概率分析与指示器变量例子

8.1. 球与盒子

把相同的秋随机投到 b 个盒子里, 问在每个盒子里至少有一个球之前, 平均至少要投多少个球?
称投入一个空盒为击中, 即求取得 b 次击中的概率
设投 n 次, 称第 i 个阶段包括第 i-1 次击中到 第 i 次击中的球, 则 pi=b−i+1b$p_i=\frac{b-i+1}{b}$
用 ni$n_i$ 表示第 i 阶段的投球数, 则 n=∑bi=1ni$n=\sum _{i=1}^b{n}_i$
且 ni$n_i$ 服从几何分布, E(ni)=bb−i+1$E(n_i)=\frac{b}{b-i+1}$,
则由期望的线性性,

E(n)=E(∑i=1bni)=∑i=1bE(ni)=∑i=1bbb−i+1=b∑i=1b1i=b(lnb+O(1))$$E(n)=E(\sum _{i=1}^b{n}_i)=\sum _{i=1}^{b}E(n_i)=\sum _{i=1}^b\frac{b}{b-i+1}=b\sum _{i=1}^b\frac{1}{i}=b(lnb+O(1))$$

这个问题又被称为 赠券收集者问题 (coupon collector’s problem), 即集齐 b 种不同的赠券, 在随机情况下平均需要买 blnb 张

8.2. 序列

抛 n 次硬币, 期望看到的连续正面的次数
答案是 Θ(logn)$\mathrm{\Theta }(logn)$
记 长度至少为 k 的正面序列开始与第 i 次抛, 由于独立, 所有 k 次抛掷都是正面的 概率为
P(Aik)=12k$P(A_{ik})=\frac{1}{2^k}$, 对于 k=2⌈lgn⌉$k=2\lceil lgn\rceil$