死去两年的算法突然开始暴击我
数学基础
函数的阶
增长的阶
描述增长率:忽略低阶项,保留最高阶项,忽略常数。
增长函数
输入规模非常大。常见记号:O,Θ,Ω,o,ω
同阶函数集合
定义Θ(g(n))={f(n)∣∃c1,c2>0,n0,∀n>n0,c1g(n)≤f(n)≤c2g(n)}为g(n)的同阶函数集合。
那么如果f(n)∈Θ(g(n))则称g(n)与f(n)同阶,记作f(n)=Θ(g(n))
证真:把g(n)除过去考虑函数单调性。
证伪:反证,设定常数值,假设n0存在。
严格低阶函数集合
定义O(g(n))={f(n)∣∀c>0,∃n0,∀n>n0,0≤f(n)≤cg(n)}为g(n)的低阶函数集合。
同样,f(n)∈O(g(n))也课简记为f(n)=O(g(n))
Θ标记更强。
高阶函数集合
Ω(g(n))渐进下界。
严格低阶函数集合
o(g(n)),去掉低阶函数集合中的常数处等号。
严格高阶函数集合
ω(g(n)),去掉高阶函数集合中的等号。
递归方程求解
替换方法
先猜后证,用归纳法
迭代方法
把方程转化为一个和式,然后求解
Master定理法
求解T(n)=aT(bn)+f(n)形式的方程,设t=logba
- 如果f(n)=O(nt−ε),ε>0是常数,那么T(n)=θ(nt)
- 如果f(n)=θ(nt−)那么T(n)=θ(ntlogn)
- 如果f(n)=Ω(nt+ε),ε>0是常数,且对于任一充分大的n,af(bn≤cf(n)),c<1是常数,那么T(n)=θ(f(n))
Akra-Bazzi方法
参见https://zhuanlan.zhihu.com/p/466537697?utm_id=0
Akra-Bazzi方法是一种用于求解线性递归式的渐近解的定理。它可以处理一些主定理不能处理的情况,例如子问题的规模不相等或驱动函数不是多项式的情况。Akra-Bazzi方法求解递归方程的步骤大致如下:
- 将递归方程写成标准形式:T(n)=f(n)+∑i=1kaiT(bin+hi(n)),其中ai>0,0<bi<1,f(n) 满足多项式增长条件,hi(n) 是一个较小的扰动项。
- 求解方程 ∑i=1kaibip=1,得到唯一的实数解 p。
- 将 p 带入公式 T(n)=Θ(np(1+∫1nup+1f(u)du)),得到 T(n) 的渐近解。
分治法
分治算法是一种将复杂问题分解为较小的子问题,递归地求解子问题,然后合并子问题的解得到原问题的解的算法设计策略。分治算法的一般设计步骤是²³⁴:
- 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
- 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
- 合并:将各个子问题的解合并为原问题的解。
分治算法适用于具有以下特征的问题:
- 该问题的规模缩小到一定的程度就可以容易地解决;
- 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;
- 利用该问题分解出的子问题的解可以合并为该问题的解;
- 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。
分治算法可以用递归或迭代来实现,通常需要一个分解函数,一个求解函数和一个合并函数。分治算法的时间复杂度一般可以用递归方程来表示,然后用主定理或者Akra-Bazzi方法来求解。
动态规划
设计步骤
- 分析优化解结构
- 递归定义最 优解代价
- 自底向上计算优化解代价并保存,获取构造优化解的信息
- 构造优化解
优化子结构的证明
动态规划的优化子结构是指一个问题的最优解可以由其子问题的最优解推导出来。要证明一个问题具有优化子结构,一般需要以下几个步骤:
- 定义问题的最优解,即目标函数或者状态转移方程;
- 假设子问题的最优解已知,根据子问题的最优解构造原问题的最优解;
- 证明假设是合理的,即不存在比假设更优的解法;
- 证明子问题之间是相互独立的,即不存在重叠子问题。
举个例子,比如求斐波那契数列第n项的值,我们可以定义状态转移方程为f(n)=f(n−1)+f(n−2),其中f(0)=0,f(1)=1。我们可以按照以下步骤证明这个问题具有优化子结构:
- 定义问题的最优解:f(n) 表示斐波那契数列第n项的值,是我们要求的最优解。
- 假设子问题的最优解已知:f(n−1) 和 f(n−2) 表示斐波那契数列第n-1项和第n-2项的值,是已知的最优解。
- 根据子问题的最优解构造原问题的最优解:f(n)=f(n−1)+f(n−2),即第n项等于前两项之和。
- 证明假设是合理的:假设存在一个更优的解法 g(n),那么 g(n) 必然也等于 g(n−1)+g(n−2),否则就不符合斐波那契数列的定义。而 g(n−1) 和 g(n−2) 又必然等于 f(n−1) 和 f(n−2),否则就不是最优解。所以 g(n)=f(n),不存在比假设更优的解法。
- 证明子问题之间是相互独立的:f(n−1) 和 f(n−2) 不包含任何公共子问题,因为它们分别依赖于不同的前两项。
因此,这个问题具有优化子结构,可以用动态规划来求解。
动态规划的分类
- 编号动态规划:输入为x1,x2,⋯,xn子问题x1,x2,⋯,xi子问题复杂度O(n)。[最大不下降子序列问题]
- 划分动态规划:输入为x1,x2,⋯,xn子问题xi,xi+1,⋯,xj子问题复杂度O(n2)。[矩阵链乘问题]
- 数轴动态规划:输入为x1,x2,⋯,xn和C,子问题x1,x2,⋯,x2,K(K≤C)子问题复杂度O(nC)。[0-1背包问题]
- 前缀动态规划:输入为x1,x2,⋯,xn;y1,y2,⋯,ym子问题x1,x2,⋯,xi;y1,y2,⋯,yj子问题复杂度O(nm)。[最长公共子序列问题]
- 树形动态规划:输入是树,问题是子树,复杂性是子树的个数[树中独立集合问题]
最长公共子序列(LCS)问题
第i前缀
设序列X=(x1,x2,⋯,xn)则Xi=(x1,x2,⋯,xi)
优化子结构
设序列X,Y,Z是X,Y的LCS,有
- xm=yn,则zk=xm=yn;Zk−1是Xm−1和Yn−1的LCS
- 对于xm=yn;如果zk=xm,Z是Xm−1和Y的LCS;否则是X和Yn−1