算法相关

大O，大\Omega,大\Theta

大O

大O表示一个函数f(x)在大于某一个数时，存在一个正数c，使得f(x)\leq cO(g(x))存在，即函数的上界函数

大\Omega

大O表示一个函数f(x)在大于某一个数时，存在一个正数c，使得c\Omega (g(x))\leq f(x)存在，即函数的下界函数

大\Theta

当一个函数的上下界函数相等时（c可不相等）

递归方程阶的计算

大胆猜测小心求证（先猜，再数学归纳法证明）

暴力求解

将递归方程暴力分解，直到括号内与1同阶为止

例   T(n)=7T(\frac{n}{7})+n

T(n)=kn+7^kT(\frac{n}{7^k})

令\frac{n}{7^k}=1，即k=\log_7 n

则T(n)=\theta (nlog_7 n)=\theta (nlogn)

Master定理（具有局限性）

用于解决形如T(n)=aT(\frac{n}{b})+f(n)的递归方程，比较n^{log_ba}与f(n)阶的关系

二者取较大者为该递推方程的阶

若二者相等，则在阶上乘logn为递推方程的阶

例T(n)=7T(\frac{n}{7})+n

\theta (n^{log_77})=\theta (n)

所以T(n)=\theta (nlogn)

分治算法

将问题分解成多个小问题，降低问题的规模

最大子数组

最大子数组有三种情况构成，一种位于中间数的左侧，一种位于中间数的右侧，最后一种跨越了中间数。在这之中，位于左侧和右侧这两种情况的子问题与最大子数组相同，所以关键就是寻找跨越中间数的最大子数组。

而跨越的最大组数组可由单侧的最大子数组相加求得。

cross-mid( A,begin,end)

mid=(bigin+end)/2

for i mid downto begin

sum+=A[i]

if sum > left-sum

left-sum=sum

max-left=i

//右侧同理

return （max-left, max-right, left-sum+right-sum)

最终代码

max(A,begin,end)

if begin=end

return (begin,end,A[begin])

mid=(begin+end)/2

(left-begin,left-end,left-max)=max(A,begin,mid)

(right-begin,right-end,right-max)=max(A,mid+1,end)

(mid-begin,mid-end,mid-max)=cross-mid(A,begin,end)

//不可由上两个式子形成，因为左右两侧的最大子数组不一定包括中间数

max(mid-max,left-max,right-max)

return//上式对应的

归并排序

T(n)=2T(\frac{n}{2})+n=\Theta(nlogn)

不断二分到只剩一个数字（2\Theta(\frac{n}{2})）进行归并，用一个空的与原数组等长数组来做中介排序，返回排好序的数字

//再排序过程中如果计数调整顺序的次数，则将此题派生为求逆序对个数

矩阵乘法

两个n阶矩阵相乘则结果矩阵中元素的值为

c_{ij}=\sum_{k=1}^na_{ik}\cdot b_{kj}

所以传统矩阵相乘的时间复杂度为\Theta(n^3)


若将矩阵分为四个n/2阶的小矩阵

C_{11}=A_{11}B_{11}+A_{12}B_{21}         C_{12}=A_{11}B_{12}+A_{12}B_{21}

C_{21}=A_{21}B_{11}+A_{22}B_{21}         C_{22}=A_{22}B_{22}+A_{21}B_{12}

此时时间复杂度为T(n)=8T(\frac{n}{2})+\Theta(n^2)=\Theta(n^3)时间复杂度并没有改变


此时时间复杂度为\Theta(n^{log_27})时间复杂度减小了

大整数乘法

当两个长度为N的大整数相乘，一般情况下需要消耗\Theta(n^2)的时间复杂度，是否可以利用分治降低时间复杂度？


则XY=(A2^{n/2}+B)(C2^{n/2}+D)

XY=AC2^n+ADn^{n/2}+BC2^{n/2}+BD

此时,时间复杂度为T(n)=4T(n/2)+\Theta(n)=\Theta(n^2)

时间复杂度并没有发生改变

倘若我们稍稍改动，j减少相乘，增加加减，尽多的利用已有的结果

XY=AC2^n+((A+B)(C+D)-AC-BD)2^{n/2}+BD

此时,时间复杂度为T(n)=3T(n/2)+\Theta(n)=\Theta(n^{log_23})

第K小元素

动态规划

与分治法类似，动态规划也是将问题划分为更小的问题进行解决，但区别在于，子问题是具有重复性的，这将大大减小时间复杂度

动态规划条件

最优子结构

当一个问题的最优解包含了子问题的最优解时，称这个问题具有最优子结构

证明时是用反证法

重叠子问题

一个子问题的解在求解中不断被利用

矩阵连乘

最优子结构证明

若m[i,j]表示Ai...Aj相乘时最少的乘法次数，m[j+1,k]表示Aj+1...Ak相乘时最少的乘法次数

则m[i,k]=m[i,j]+m[j+1,k]+ri×rj×rk

重叠子问题证明


所以构建二维矩阵m[i,j]用于存储某个区间内矩阵相乘最少的乘法次数，i表示开始的矩阵下标，j表示结束的矩阵下标

m[i,j]=min(m[i,k]+m[k+1,j]+ri×rk×rj), i<j

m[i,j]=0, i\geq j

钢条切割

最优子结构

当最终是最大收益时，切割下来的每一部分也是当前长度的最大收益

重叠子问题


m(n)=\max_{1\leq i\leq n}(p_i+m(n-i))

最长公共子序列

二维矩阵m[i,j]表示Xi和Yj中最长公共子序列的长度

m[i,j]=1/0,                                         i=j

m[i,j]=m[i-1,j-1]+1,                                X[i]=Y[j]

m[i,j]=max{m[i-1,j],m[i,j-1]},              i≠j，X[i]≠Y[j]

0/1背包问题

背包中物品只可整个装入或者取出，不可部分装入取出

dp[i][j]表示物品为i，i+1，...，n，背包容量为j时的最优解

dp[i][j]=max(dp[i+1][j],dp[i+1][j-p_i]+v_i),j\geq p_i

dp[i][j]=dp[i+1][j]                                                                            j<pi  

dp[n][j]=0                                                                                       j=0

dp[n][j]=pn                                                                                     j≥vn

贪心算法

活动选择问题（ 最少圆覆盖最多点）

选择活动结束时间最早的活动，下一个活动为开始时间比现有活动晚且结束时间最早的活动。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容