算法概论笔记

算法概论

序言

时间复杂度

  1. 常数项可忽略
  2. 当 a > b 时,\(n^a\) 支配 \(n^b\)
  3. 任何指数项支配任何多项式项
  4. 任何多项式项支配对数项:n 支配 \((logn)^3\)

\(e^{\frac{1}{2}\ln{n}}\)\(5^{\ln{n}}\)

一个事实:在大 \(\Theta\) 符号意义下,当几何级数(\(c^k\))严格递减(c<1)时,几何级数的可以简化为首项;当级数严格递增(c>1)时,几何级数的和可以简化为末项;当级数保持不变时(c为1),几何级数的和可以简化为项数。

复杂度分析小窍门

  • 若两段算法分别有复杂度\(T_1(n)=O(f_1(n))\)\(T_2(n)=O(f_2(n))\),则
    • \(T_1(n)+T_2(n)=max(O(f_1(n)), O(f_2(n)))\)
    • \(T_1(n){\times}T_2(n)=O(f_1(n){\times}f_2(n))\)
  • \(T(n)\) 是关于 \(n\)\(k\) 阶多项式,那么 \(T(n)=\Theta(n^k)\)
  • 一个 for 循环的时间复杂度等于循环次数乘以循环体代码的复杂度
  • if-else 结构的复杂度取决于 if 的条件判断复杂度和两个分支部分的复杂度,总体复杂度取三者中最大

==通常,将问题整体数学化后再进行算法设计,可以极大地优化复杂度==

数字的算法

常见运算的复杂度

  • 加法:\(O(n)\)
  • 乘法:日常:\(O(n^2)\),分治+Gauss:\(O(n^{1.59}\),快速 FT
  • 模:
    • 模的加法:\(O(n)\)
    • 模的乘法:\(O(n^2)\)
    • 模的除法:\(O(n^3)\):先用辗转相除法求出除数的逆元,再乘之
    • 模的指数:\(O(n^3)\)\(x^y mod z=(x^{y/2})^2 mod z\)
  • 最大公因数:\(O(n^3)\):更相减损法:\(gcd(x, y)=gcd(x-y, y)\)

数论

替代准则

若有 \(x{\equiv}x'(mod N)\)\(y{\equiv}y'(mod N)\) 成立, 则有:\(x+y{\equiv}x'+y'(mod N)\)\(xy{\equiv}x'y'(mod N)\)

Euclid 规则(更相减损法)

\(x\)\(y\) 是正整数,且有 \(x{\geq}y\),则 \(gcd(x, y)=gcd(x mod y, y)\)

故:\(gcd(x, y)=gcd(x-y, y)\)

扩展 Euclid 规则(辗转相除法)

\(d\) 整除 \(a\)\(b\),同时存在整数 \(x\)\(y\),使得 \(d=sx+by\) 成立, 那么一定有 \(d=gcd(a,b)\)

\[d=gcd(a,b)=gcd(b,a mod b)=bx'+(a mod b)y'\] \[=bx'+(a-\lfloor\frac{a}{b}\rfloor{b})y'=ay'+b(x'-\lfloor\frac{a}{b}\rfloor{y'})\]

\(d=ax+by\),其中 \(x=y'\)\(y=x'-\lfloor\frac{a}{b}\rfloor{y'}\)

模的除法定理

对于任意的 \(a mod N\)\(a\) 有一个模 \(N\) 的乘法逆元,当且仅当 \(a\)\(N\) 互素。

Fermat 小定理

\(p\) 为一个素数,则对任意 \(1\leq{a}<p\),有 \(a^{p-1}\equiv1(mod p)\)

如果把后面的结论作为条件,则 \(p\) 大概率为素数

Lagrange 素数定理

\(\pi(x)\)\(\leq{x}\) 的素数的个数,则有 \(\pi(x)\approx\frac{x}{ln(x)}\)

一个随机 n 位长的数字为素数的概率约为 \(\frac{1}{ln(2^n)}\approx\frac{1.44}{n}\)

随机算法

许多算法依赖于概率,其输出不一定准确,但是大概率准确。

可以分为两类: 1. Monte Carlo 算法:运行快,结果大概率正确 2. Las Vegas 算法:结果准确,运行大概率快

通用散列表

对于任意四个系数 \(a_1,\dots,a_4\in\{0,1,\dots,n-1\}\),记 \(a=(a_1,a_2,a_3,a_4)\), 定义散列函数 \(h_a(x_1,\dots,x_4)=\sum^4_{i=1}a_i\cdot{x_i}mod n\)

若系数 \(a=(a_1,a_2,a_3,a_4)\) 为随机均匀选取,则有 \[Pr\{h_a(x_1,\dots,x_4)=h_a(y_1,\dots,y_4)\}=\frac{1}{n}\] ,即两个数据别名相同的概率

通常把 \(h_a(x_1,\dots,x_4)\) 称为 \(x\) 的别名

散列表应用步骤: 1. 将散列表的大小 n 定为一个素数,其比将要存在该表中的期望数据项数目稍大,一般为两倍左右 2. 设所有数据项取值范围为 \(N=n^k\) 3. 每个数据项可以视为一个关于模 n 操作的 k 元组,而 \(H=\{h_a:a\in\{0,\dots,n-1\}^k\}\) 即为一个通用散列函数族

由于系数(即散列函数族)为随机均匀选取时,两个数据别名相同的概率很小, 故散列表性能很好,几乎为线性,而且空间复杂度也很小

插播一条高数:\(n!\geq\frac{n!}{(n/2)!}\geq\frac{n}{2}^\frac{n}{2}\)

分治算法

乘法

\[xy: O(n^2)\] \[xy=(2^{n/2}x_H+x_L)(2^{n/2}y_H+y_L)\] \[=2^nx_Hy_H+2^{n/2}(x_Hy_L+x_Ly_H)+x_Ly_L:\] \[O(n^{ln3}),\] \[with x_Hy_L+x_Ly_H=(x_H+x_L)(y_H+y_L)-x_Hy_H-x_Ly_L\]

插播一条高数:\(O(3^{\log_2n})=O(n^{\log_23})\)

递推式

分治算法通常遵循: - 对于规模为 n 的问题,先递归地求解 a 个规模为 n/b 的子问题 - 然后在 \(O(n^d)\) 时间内将子问题的解合并起来 - 故运行时间为 \(T(n)=aT(\lceil{n/b}\rceil)+O(n^d)\) 1. 若 \(d>\log_ba, T(n)=O(n^d)\) 2. 若 \(d=\log_ba, T(n)=O(n^d\log{n})\) 3. 若 \(d<\log_ba, T(n)=O(n^{\log_ba})\) - 又称 主定理

合并排序

\(O(n\log{n})\)

  1. 将数列分为前后两部分,递归地对每一部分进行排序(最终每部分都为单元素数列)
  2. 将两个排好的有序数列 \(x[1...k], y[1...l]\) 合并为新数列 \(z\)
    1. 新数列的第 1 个为 \(x[1], y[1]\) 中小的
    2. 类似第一步进行递归

寻找中项

将寻找中位数抽象为更一般的:寻找第 k 小的数

在数列中,随机选取一个数 v,并将数列分为 \(>v, =v, <v\) 三个子列,则第 k 小的数一定落在其中一个子列中,且每个子列的长度已知。故只需搜索一个子列即可。

该算法依赖于 v 的好坏,平均为 \(O(n)\),最差为 \(\Theta(n^2)\)

快排与之思路一致

矩阵乘法

\[XY=\begin{bmatrix}A&B\\C&D\end{bmatrix}\begin{bmatrix}E&F\\G&H\end{bmatrix}\] \[=\begin{bmatrix}AE+BG&AF+BH\\CE+DG&CF+DH\end{bmatrix}\] \[=\begin{bmatrix}P_5+P_4-P_2+P_6&P_1+P_2\\P_3+P_4&P_1+P_5-P_3-P_7\end{bmatrix}\]

其中 - \(P_1=A(F-H)\) - \(P_2=(A+B)H\) - \(P_3=(C+D)E\) - \(P_4=D(G-E)\) - \(P_5=(A+D)(E+H)\) - \(P_6=(B-D)(G+H)\) - \(P_7=(A-C)(E+F)\)

\(T(n)=7T(n/2)+O(n^2)\),最终复杂度为 \(O(n^{\log_27})\)

快速 Fourier 变换

以多项式相乘为出发点

性质

一个 d 次 多项式被其在任意 d+1 个不同点处的取值所唯一确定。

常见例子:两点确定一条直线

多项式相乘的分治实现

  • 要计算 d 次多项式 \(A(x)\)\(B(x)\) 的乘积 \(C(x)\),先选取 n 个点 \(x_0, x_1,\dots,x_{n-1}\),其中 \(n\geq2d+1\);
  • 对每个点 \(x_k\),计算 \(A(x_k)\)\(B(x_k)\)
  • 对每个点 \(x_k\),计算 \(C(x_k)=A(x_k)B(x_k)\)
  • 插值得到 \(C(x)=c_0+c_1x+\dots+c_{2d}x^{2d}\)

快速 Fourier 中,将这 n 个点选取为: \[\pm{x_0},\pm{x_1},\dots,\pm{x_{\frac{n}{2}-1}}\]

这利用了 \(x_i\) 的偶次幂 等于 \(-x_i\) 的偶次幂来减少运算

\[A(x_i)=A_e(x_i^2)+x_iA_o(x_i^2)\] \[A(-x_i)=A_e(x_i^2)-x_iA_o(x_i^2)\]

如此,计算时间缩短一半

若能递归使用,即 使用同样的方法计算 \(A_e\)\(A_o\),则能得到 \(O(n\log{n})\),其中须取复数 \(x_i\),则生成的新的自变量中存在相反对,可以作为下次的自变量

这就得到了快速 Fourier 算法:

  • function \(FFT(A,\omega)\)
  • Input: n 次 \(A(x)\) 的系数表达,其中 n 是 2 的幂,\(\omega\) 是单位元 1 的 n 次方根
  • Output: \(A(x)\) 的值表达:\(A(\omega^0),\dots,A(\omega^{n-1})\)
  • 算法见书 P74

插值

FFT:从系数表达到值表达: - <值> = FFT(<系数>, \(\omega\))

插值:从值表达到系数表达: - <系数> = \(\frac{1}{n}\)FFT(<系数>, \(\omega^{-1}\))

学不下去了,下一章!

Licensed under CC BY-NC-SA 4.0