***************************************转载请注明出处：http://blog.csdn.net/lttree********************************************

我的这系列文章参考的书是: 王晓东 的 《计算机算法设计与分析》（第4版）

首先，当然是第一章节的概述，这些东西简要说一下概念：

1.算法与程序的区别？

——算法 指 解决问题的一种方法 或 一个过程

（严格的讲，算法是由若干条指令组成的有穷序列）

——程序 指 算法用某种设计语言的具体实现。

通俗的讲，算法是一个想法，idea，而程序是对算法的实现。 

2.算法复杂性与渐进表达式

这个问题书上有大规模的概述，看的头晕啊，我缩短一下。

第一，算法的复杂性（C）与三个问题相关：所求解问题的规模（N）、算法的输入（I）、算法本身（A）。

用式子表示： C = F（N，I，A）

其中，算法本身（A）一般隐含在在复杂性函数名中，再将复杂性分为 时间复杂性（T）和空间复杂性（S）。

T = T（N，I）

S = S（N，I）

并且，由于空间复杂性计算方法比较简单，并且两者计量方法相似，所以一般情况下，都只讨论时间的复杂性，本书也是主要讨论时间复杂性。

对于时间复杂性的讨论，有三种情况：

— 最坏情况 — 最好情况 — 平均情况

上述三种情况，各有各的用处与局限性，也能从某一角度反映算法效率。但实践表明，可操作性最好且最有实际价值的是最坏情况下的时间复杂性。

再有就是 渐近态 和 渐近表达式

渐近态就是 4 个符号：

O、Ω、θ、o

——O 是上界，

——Ω 是下界

——θ 是同阶

——o 是低阶

渐近表达式，就要记住一点，对于渐近性分析只要关心时间复杂性的阶，无须关心它的常数因子。

—— 3n^2+10n  渐近表达式为 O（n^2）

—— 21 + 1/n  渐近表达式为 O（1）

—— 10n + 10n 渐近表达式为 O（n）

3.最后就是 NP 完全性理论了

这个问题，比较复杂也很经典，我看书没太看懂，又上网充了充电，下面是我的理解，如有错误，欢迎指出。

首先是 Polynomial问题（P问题）

能够在多项式时间内求解的判定问题。

然后是 Non-Deterministic Polynomial问题（NP问题）

对于一个问题，无法找到一个在多项式时间内解决的方法，于是就需要多次验证，来看能否解决，显然这是很费时间的。

而更加进阶的 Non-Deterministic Polynomial Complete 问题（NPC问题）

这个就是在NP问题基础上，将每一种情况都完全验证，就是将所有情况都穷举了，这就是NPC问题，也就是NP问题中最麻烦的一种。

这就是我对 P、NP、NPC问题的看法了。

如果文章有什么错误，敬请斧正。

***************************************转载请注明出处：http://blog.csdn.net/lttree********************************************

重拾算法之路——算法概述及NP完全性理论