算法设计与分析总结
<h2>一、 算法引论</h2>
<ul>
<li>
<p>算法分析的目的：估算该算法所需的内存空间和运行时间。</p>
</li>
<li>
<p>分析算法复杂度的目的：用以比较同一问题的不同算法；时间和空间的增长率作为衡量的标准。</p>
</li>
<li>
<p>算法是对解决这个问题的方法和步骤的描述。</p>
</li>
<li>
<p>算法的基本特征：有穷性、确定性、可行性、0到多个输入、1到多个输出。</p>
</li>
<li>一个好的算法应具有正确性、可读性、健壮性和高效性和低存储量需求等特征。</li>
</ul>
<h2>二、 递归与分治策略</h2>
<ul>
<li>
<p>递归的概念：直接或者间接的调用自身的算法。</p>
</li>
<li>
<p>递归函数：用函数自身给出定义的函数。</p>
</li>
<li>
<p>构成递归式的两个基本条件：递归的边界条件和递归的定义（递归公式）。</p>
</li>
<li>分治法的基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归的解决这些子问题，然后将各个子问题的解合并得到原问题的解。</li>
</ul>
<h2>三、 动态规划</h2>
<p>简述动态规划算法解题的基本步骤：</p>
<ol>
<li>
<p>找出最优解的性质，并刻画其结构特征；</p>
</li>
<li>
<p>递归的定义最优值；</p>
</li>
<li>
<p>用自底向上的方法计算最优值；</p>
</li>
<li>根据计算最优值时得到的信息，构造最优解；</li>
</ol>
<p>简述动态规划和分治法的异同。</p>
<p>相同点：动态规划与分治法类似，其基本思想也是将待求解的问题分解成若干子问题，然后从这些子问题的解得到原问题的解。</p>
<p>不同点：分治法的子问题互相独立且与原问题相同；动态规划求解的问题，经分解得到的子问题，往往不是相互独立的，就是各个子问题包含公共的子问题。</p>
<p>动态规划的基本要素：</p>
<ul>
<li>
<p>最优子结构</p>
</li>
<li>重叠子问题</li>
</ul>
<p>简述备忘录方法与动态规划的异同:</p>
<ul>
<li>
<p>相同点：备忘录方法和动态规划都有相同的控制结构。</p>
</li>
<li>不同点：备忘录方法的递归方式是自顶向下，动态规划则是自底向上；备忘录方法通过建立备忘录避免了相同子问题的重复求解。</li>
</ul>
<p>快速排序算法的性能取决于划分的对称性。</p>
<h2>四、 贪心算法</h2>
<p>贪心算法的基本条件：</p>
<ul>
<li>
<p>贪心的选择性质</p>
</li>
<li>最优子结构性质</li>
</ul>
<p>简述动态规划和贪心算法的异同：</p>
<ul>
<li>
<p>相同点：都有最优子结构性质。</p>
</li>
<li>不同点：贪心具有贪心选择性质（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来到达）；动态规划通常以自底向上的方式解各个子问题，贪心算法通常以自顶向下的方式进行。</li>
</ul>
<p>简述Prim算法和Kruskal算法的异同：</p>
<ul>
<li>
<p>相同点：都可以运用贪心算法构造最小生成树，都利用了最小生成树的性质。</p>
</li>
<li>不同点：Prim算法通过扩展连通子集来进行贪心选择；Krusikal算法通过选择具有最小权的边的集合来进行贪心选择，在选择时，进行连通操作以便生成树。</li>
</ul>
<h2>五、 回溯算法</h2>
<p>回溯解题的步骤：</p>
<ol>
<li>
<p>针对所给问题定义问题的解空间。</p>
</li>
<li>
<p>确定易于搜索的解空间结构。</p>
</li>
<li>以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效的搜索。</li>
</ol>
<p>回溯法搜索解空间树时常用的两种剪枝函数为约束函数和界限函数。</p>
<h2>六、 分支界限算法</h2>
<p>简述分支界限法的搜索策略：</p>
<ol>
<li>
<p>以宽度优先和以最小耗费（最大效益）优先的方式搜索问题的解空间树。</p>
</li>
<li>
<p>每个活节点只有一次成为扩展节点</p>
</li>
<li>
<p>活节点成为扩展节点就一次性生成其所有的子节点。</p>
</li>
<li>
<p>儿子节点中，导致不可行节点和非最优节点的节点被舍弃，其余节点加入到活节点表中，当前活节点从表中删除。</p>
</li>
<li>从活节点中取出下一个节点成为当前扩展节点，并重复上述节点扩展过程。一直搜索到解或者活节点表为空为止。</li>
</ol>
<p>分支界限法：队列式分支界限法和优先队列式分支界限法。</p>
<p>活节点的组织形式有：最大堆和最小堆。</p>
<p>简述分支界限法和回溯法的异同：</p>
<ul>
<li>
<p>相同点：都是对子集树和排列树的搜索。</p>
</li>
<li>不同点：求解目标不同，分支界限法的求解目标是找出满足约束条件的一个解，或是在满足约束的解中找出某种意义的最优解；回溯法找到的是解空间满足约束条件的所有解。搜索策略不同：分支界限法以广度优先搜索或以最小花费优先的方式进行搜索；回溯法以深度优先搜索的方式进行搜索。</li>
</ul>
<p>七、 概率算法</p>
<ul>
<li>
<p>数值概率算法求近似解，精度和时间成正比。</p>
</li>
<li>
<p>蒙特卡罗算法求的是准确解，但未必正确，正确率和时间成正比。</p>
</li>
<li>
<p>拉斯维加斯算法不会得到不正确解，得到正确解的概率和时间成正比。</p>
</li>
<li>舍伍德算法总能得到解，并且解一定是正确的。最坏时间复杂度和平均时间复杂度差距很大时，可用舍伍德算法进行平均。</li>
</ul>
<p>八、 NP完全性理论</p>
<ul>
<li>
<p>P类问题：P={L|L是一个能在多项式时间内被一台DTM所接受的语言}。由此语言定义的问题。</p>
</li>
<li>
<p>NP类问题：P={L|L是一个能在多项式时间内被一台NDTM所接受的语言}。由此语言定义的问题。</p>
</li>
<li>NPC问题：（1）L属于NP；（2）对于所有L'属于NP有L'正无穷PL；由此语言定义的问题。</li>
</ul>