NP问题
1 时间复杂度时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。 不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。 还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。不会存在O(2n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此，我们会说，一个O(0.01n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候...
1 算法概述
算法概述 参考文献 八种算法思想 1 基本概念定义 算法是一系列解决问题的清晰指令，对于符合一定规范的输入，算法能够在有限时间内获得所要求的输出。算法是解决问题的一种方法或过程，它是由若干条指令组成的有穷序列。 算法本质上不是数学，而是逻辑。 特征 输入：有零或多个外部量作为算法的输入。 输出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有效性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 算法的描述 算法的描述方式：自然语言、流程图、伪代码 算法的正确性证明方式：归纳法 算法分析：正确性分析、效率分析、复杂度分析 算法的终极目标 次序order：先做什么、后做什么。前边对后边有影响。 选择if-else：要做什么、不做什么。合并相同的类别，减少分类讨论的情况。 重复while-for:一直做什么。提取相同子结构、相同子操作，进行重复利用。可以通过递归实现重复。 整理说明 以算法结尾，代表的是某一系列或者某一类通用的算法。不依赖于具体的问题。通常可以解决很...
2 算法效率
算法效率 目录 算法效率的度量 函数的渐进的界 算法的基本复杂性类型 算法复杂性分析的基本方法 非递归算法的复杂性分析 递归算法的复杂性分析 递归算法与非递归算法比较 经验分析方法 算法可视化 1 算法效率的度量分类 时间复杂度 空间复杂度 算法效率的表示N-要解决问题的规模I-算法的输入A-算法本身C-算法复杂性S-空间复杂性T-时间复杂性$$C = F(N, I, A)\T = T(N, I)\S = S(N, I)\$$ 算法效率的界包含最大时间效率、最小时间效率、平均时间效率。 2 函数的渐进的界函数的界定义设f 和g 是定义域为自然数集N上的函数 $f(n)=O(g(n))$渐进上界若存在正数$c$和$n0$使得对一切$n≥n0有0≤f(n)≤cg(n)$ $f(n)= Ω(g(n))$渐进下届若存在正数$c$和$n0$使得对一切$n≥n0有0≤cg(n)≤ f(n)$ $f(n)=o(g(n))$不可达上届对任意正数$c$存在$n0$使得对一切$n≥n0$有$0≤f(n)<cg(n)$ $...
4 分治法
分治法1 分治法概述基本思想 求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。 分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同类型的子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。 分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。 分治法解决问题的先决条件 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 分治法的步骤一般来说，分治法的求解过程由以下三个阶段组成： 划分divede：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。 解决conquer：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。 合并merge：把各个子问题的...
5 动态规划
动态规划 参考文献 https://zhuanlan.zhihu.com/p/144655170 https://www.cxyxiaowu.com/6781.html https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486923&idx=2&sn=6c1c8aeb4db68522e67ddf8c1e933660&chksm=fa0e624acd79eb5cdb410808921609a830b9b9221e813e4eb89cf551ca48f317668d44b095d2&scene=21#wechat_redirect https://www.cxyxiaowu.com/7012.html 1 概述基本思想 多阶段决策问题。比如最短路线问题，机器负荷问题等，把解决这一类问题的的方法称为动态规划方法 动态规划算法与分治法类似，其思想把求解的问题分成许多阶段或多个子问题，然后按顺序求...
5.1 矩阵连乘问题
矩阵连乘问题问题描述给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。例如，给定三个连乘矩阵{A1，A2，A3}的维数分别是10*100，100*5和5*50，采用（A1A2）A3，乘法次数为10*100*5+10*5*50=7500次，而采用A1（A2A3），乘法次数为100*5*50+10*100*50=75000次乘法，显然，最好的次序是（A1A2)A3，乘法次数为7500次。 问题分析矩阵链乘法问题描述：给定由n个矩阵构成的序列｛A1，A2，…，An}，对乘积A1A2…An，找到最小化乘法次数的加括号方法。 策略选择 算法思想：动态规划 算法设计 问题分解划分阶段：相邻连乘的个数。相邻连乘的个数为1，的时候0次乘法。两个相邻连乘的次数固定。三个相邻连乘的时候分两次讨论。规模增长的方向主要由两个一个是k表示矩阵连乘的个数，第二个是i表示矩阵的个数。 确定状态变量：dp[k][i]。表示连乘为k的时候，第i个矩阵开始的最优的乘积方式。 确定状态转移...
6 贪心算法
贪心算法概述思想 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。 特点 贪心算法不能对所有问题都得到整体最优解。但对许多问题他能产生整体最优解，或者最优解的近似。 贪心算法中较大子问题的解敲好包含了较小子问题的解作为子集。与动态规划算法中的优化原则本质上一致。 动态规划算法在某一步决定优化函数的最大或最小值时，需要考虑他的所有子问题的优化函数的值。然后从中选出最有的结果。贪心算法的每步判断时，不考虑子问题的计算结果，而是根据当前的情况采取“只顾眼前”的贪心策略决定取舍。 贪心算法的适用条件 最优子结构性质 一个问题的最优解包含其子问题的最优解。问题具有最优子结构性质时，可以用动态规划算法或者贪心算法求解。 贪心选择性质 所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 动态规划算法通常是自底向上的方式来求解各个子问题。贪心算法同行一自顶向下的方式，一迭代的方式作出相机的谈心选择。每左慈谈心选择就将所求问题简...
7 回溯法
回溯法0 概述基本思想 回溯法是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯法的基本思想：该方法系统地搜索一个问题的所有的解或任一解。 与剪枝相结合，也称为回溯-剪枝法。 深度优先搜索与回溯剪枝这两个思想有一个非常重要的优势。它是一条路经走到黑。如果这条路径合适的话，就可以直接返回。另外。当前所有的搜索选项中，只有一条路径在工作。也就是说只需要记录当前一条路径的状态。所以解决迷宫问题的时候，不需要复杂的状态记录方法。只需要记录当前这一个分支的路径状态即可。 要素 解向量-问题解的表示：回溯法将问题的解表示成n元式$(x_1,x_2,\cdots,x_n)$。 显示约束：对分量xi的取值限定。 隐式约束：对满足问题的解而对不同分量之间施加约束 解空间：对于一个实例，解向量满足显示约束条件的所有多元组，构成了该实例的一个解空间。 回溯法的适用条件 适用于搜索问题和优化问题 多米诺性质：叶子节点的解一定...
8 分支限界
分支限界1 概述基本思想 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 常见的两种分支界限法 队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 使用条件 问题的多米诺性质叶子节点的解一定满足其父节点。叶子结点为真则父节点一定为真。同理父节点为假则叶子结点一定为假（逆否命题）。用父节点为假的情况进行剪枝操作。 求解最优解或一个可行解 设计要素 针对问题定义解空间 问题解向量 解向量分量取值集合 构造解空间树 判断是否满足多米诺性质 确定剪枝函数 确定存储搜索路径的数据结构 分支限界发的核心思想在于界的设计 分支限界法的程序结构 队列+循环的方法 2 分治限界实现...
9 随机化
随机化算法随机算法的概述 将算法必须对所有可能的输入都正确地求解问题的条件放宽，只要求它的可能不正确性解能够相对安全地忽略掉，比如说它的出现可能性非常低;而且也不要求对于特定的输入，算法的每一次运行的输出都必须相同。 随机算法可以做如下定义：它是在接收输入的同时，为了随机选择的目的，还接收一串随机比特流并且在运行过程中使用该比特流的算法。 一个随机算法在不同的运行中对于相同的输入可以有不同的结果。由此得出对于相同的输入两次不同的随机算法的执行时间可能不同。 随机算法的优点 首先，较之那些我们所知的解决同一问题最好的确定性算法，随机算法所需的运行时间或空间通常常小一些； 其次，观察迄今为止已经发明的各种随机算法，我们发现这些算法总是易于理解和实现。 1 伪随机数伪随机数的产生$$\begin{cases} a_0=d\ a_n=(ba_{n-1}+c) mod m\end{cases}$$ 其中$a\geq 0,b\geq0,d\geq m,d$是随机序列种子。 2 数值随机化算法3 舍伍德算法 确定性算法随机化。 4 蒙特卡洛算法 蒙特...
