算法设计与分析|5个算法

《算法分析与设计》课程是理论性与应用性并重的专业课程。本课程以算法设计策略为知识单元，系统地介绍计算机算法的设计方法和分析技巧。课程教学主要内容包括：第一章，算法概述；第二章，递归与分治策略；第三章，动态规划；第四章，贪心算法；第五章，回溯法；第六章，分支限界法。通过介绍经典以及实用算法让同学掌握算法设计的基本方法。结合实例分析，让同学深入理解算法设计的技巧，以及分析算法的能力。

2、典型问题的Java应用示例分布在不同的章节中。此外，书中以大量图例说明算法的工作过程，使算法更加易于理解和掌握，本书适合作为高等院校计算机专业本科生和研究生算法设计课程的教材，也可作为从事软件开发和工程设计的专业人员的参考书。此外，算法爱好者和参加各种程序设计大赛的选手也可把本书作为参考用书。

  三类问题都会涉及到多项式时间算法，我们先解决什么是多项式时间算法。

  多项式时间的算法的形式化定义是，对于规模为n的输入，在最坏情况下的运行时间是 ，其中k为某一 确定常数 。相对应的，有伪多项式时间算法，典型的0-1背包问题算法复杂度为 ，其运行时间与输入的规模相关，是伪多项式的。

  如以下表格中的都是P类问题。

  NP问题能找到多项式时间的验证算法。

  什么叫验证？例如，在哈密尔顿圈问题中，Z为图中点的一个序列。如果我们能设计一个多项式时间的判定算法，判定这个序列是否是一个哈密尔顿圈，那么称这个问题能在多项式时间内验证，序列Z是这个问题的一个证书（Certificate）。

如何证明一个问题是NP问题？

注意 ：不用证明这个问题没有多项式时间求解算法，因为P类问题是NP问题的子集，只需有证书验证过程即可。

   非形式化定义 ，如果一个NP问题和其他任何NP问题一样“不易解决”（归约），那么我们认为这一问题是NPC类问题或称之为NP完全问题。

   形式化定义 ，问题X是NP完全的，如果：

  NP问题可在多项式时间归约到NPC问题。特殊地，如果一个问题满足2，而 不一定 满足1，则称它是NP难度（NP-Hard）的。

  反过来，要证明一个问题Y是NP完全的。可以采用如下步骤：

写了这么多，我还是看不懂。就这样理解叭，P类问题是可以在多项式时间求解的问题，但大部分问题都是不能的。因此我们想用一些数据去验证它是不是这个问题的解，如果能在多项式时间验证出来，那么这个问题就是NP问题。其中，NP里最难的问题我们叫它NPC问题，但有些问题跟NPC问题差不多难，然而它又不是NP问题，就只好说它是NP难度的，也就是NP难问题（NP-Hard）。

  目的：我们希望在多项式时间内解决一个 判断 问题。

  准备：某一特定问题（A）的输入为该问题的实例。例如，寻找路径（PATH）问题的实例可以是图G、G中特定的点u和v以及一个特定的整数k（是否存在u到v长度为k的路径）。

  假设有另一不同的判定问题B，已知在多项式时间解决它的算法。我们将A的任何实例 α 转化成B的具有以下特征的某个实例 β：

  这一过程就是 多项式时间归约算法 。它提供了一种在多项式时间内解决A的方法：

参考资料 ：《算法导论》

总结算法设计的步骤

弄清楚题目的意思，列出题目的输入、输出、约束条件

思考怎样让算法的时间复杂度尽可能的小

编写伪代码或代码

归纳思维

是从特殊情况出发

推理出一般性的结论

作为数据分析的重要思维，应该引起足够的重视。

扩展：介绍 5 种归纳方法，即：求同法、求异法、共用法、共变法和剩余法，其实这些方法早在古代就有，后来培根在《新工具》一书中进行了概括和归纳，最后由穆勒加以系统的整理和说明，因此通常称为「穆勒五法」。