返回

几个核心问题

时间复杂度总结

问题 时间复杂度 备注
二分搜索 $O(logn)$
大整数的乘法 $O(n^2)$或$O(n^{log_23})$…..
Strassen矩阵乘法 $O(n^3)$$O(n^{log_27})$$O(n^{2.376})$
合并排序 $O(nlogn)$
快速排序 最坏$O(n^2)$最好$O(nlogn)$
线性时间选择 $O(n)$
最接近点对问题 $O(nlogn)$
矩阵连乘 $O(n^3)$ 最优值在dp[0][n]处
最长公共子序列 $O(mn)$ and $O(m+n)$ 最优值在dp[m][n]处
最大子段和 $O(mn^2)$或$O(m(n-m))$ 最优值在dp[n]处
凸多边形最优三角剖分 $O(n^3)$ 最优值在dp[0][n]处
流水作业调度 $O(nlogn)$ 最优值在dp[m][n]处
0-1背包问题 $O(min{nc,2^n})$ 最优值在dp[i][j]处
活动安排问题 $O(nlogn)$
最优装载 $O(nlogn)$
哈夫曼编码 $O(nlogn)$
最小生成树 P$O(n^2)$ K$O(eloge)$
多机调度问题 $O(nlogn)$
装载问题 不记录$O(2^n)$,记录可以$O(2^n)和O(n2^n)$
批处理作业调度 $O(n!)$
符号三角形问题 $O(n2^n)$
n后问题 $O(n!)$
最大团问题 $O(n2^n)$
旅行售货员问题 $O(n!)$

分支界限法不考虑复杂度,至少书上没写。

迭代法证明时间复杂度

$T(n)=aT(n/b)+f(n)$

设$n=b^k$则有

image-20211117234705474
image-20211117234705474

image-20211117234713208
image-20211117234713208

dp方程

矩阵连乘问题

$$\begin{equation} dp[i][j]= \begin{cases} 0& \text{i=j}\ min_{1<k\leq j}(dp[i][k]+dp[k+1][j]+p_{i-1}p_kp_j& {i\neq j} \end{cases} \end{equation}$$

公共子序列

image-20211113204101376
image-20211113204101376

流水作业调度

image-20211113221352259
image-20211113221352259

0-1背包问题

image-20211118000619916
image-20211118000619916

石子合并

两次矩阵连乘吧,背不会了

image-20211118000710883
image-20211118000710883

独立调度

image-20211118000724100
image-20211118000724100

最小子结构证明

image-20211118001402052
image-20211118001402052

image-20211118001410914
image-20211118001410914

image-20211118001502278
image-20211118001502278

image-20211118001513992
image-20211118001513992

贪心选择

最优装载

image-20211118001615649
image-20211118001615649

哈夫曼树

image-20211118001643706
image-20211118001643706

分支界限法的细节

首先队列的方案就不用多说了。就是一个队列+BFS。主要是优先队列的分支界限。

首先是0-1背包问题:

在这里插入图片描述
在这里插入图片描述

我们按照单位质量最高的排序,up表示当前可以实现的最优解。所以对于上述的树,首先是判断x1是否放入,如果放入,此时背包质量为4,价值为40,可能的最高价值为76。因为价值高于右子树,所以继续左子树遍历。接下来判断x2是否放入,显然,放不下,所以只能不妨,此时可能的最高价值为69,仍高于根节点的右子树。继续,判断x3是否放下,发现不仅可以放下,而且其可能的期望价值是高于不放的,所以右子树删掉,继续判断x4。发现放下去会超出背包重量,所以选择不妨,但是此时我们也能发现最优解的价值已经超过了右子树的价值,所以没必要继续遍历了。

接下来是装载问题。

在这里插入图片描述
在这里插入图片描述

比较类似,只不过初始没有排序,而且这个例子比上面的复杂一点。x1还是放与不妨,但是放不放都挺好,所以先生成左子树,接着生成右子树。对于x2,第二个物品放不下去,所以不放,此时剩余物品的期望是13,但不是bestw,所以开始遍历根节点右子树的情况…

旅行商售货问题:

在这里插入图片描述
在这里插入图片描述

其他的

算法的要素:输入、输出、有限性、确定性

时间复杂度:

image-20211118001830872
image-20211118001830872

NP完全理论:

image-20211118001846085
image-20211118001846085

回溯法剪枝:是否超过约束条件、是否超出最优解。可能要画解空间

分支界限法:画队列变化情况

f

Licensed under CC BY-NC-SA 4.0
豫ICP备2021032923号
Built with Hugo
Theme Stack designed by Jimmy