第1章 算法概述

1.1算法与程序

算法的概念： 通俗地说，算法是指解决问题的一种方法或一个过程。

严格地讲，算法是由若干条指令组成的有穷序列。且满足4条性质：

（1）输入 

（2）输出

（3）确定性 ：指令清晰，无歧义

（4）有限性：执行次数有限，执行时间有限。

1.2算法复杂性分析

算法复杂性有时间复杂性和空间复杂性，

时间复杂性常用 渐进表达式（保留主项、忽略其余较低的项）表示。

如果几个算法的渐进复杂性阶数不同，只要确定阶数，即可判断哪个算法的效率高。 可以使用记号O来描述阶数。

O符号定义：若存在自然数N0和正常数C，使得当N>=N0时，f(N)<= Cg(N),则称f(N)当N充分大时上有界，g(N)是它的一个上界。

记为f(N)=O(g(N))。这时还说f(N)的阶不高于g(N)的阶。

例：3N=O(N)

2N^2 + 10N=O(N^2)

1.3 NP完全性理论                                           //此处略过。。。

可以在多项式时间内求解的判断问题构成P类问题。

非确定性多项式问题（验证容易）的问题是NP类问题。