1.1算法与程序
算法是指解决问题的一种方法或一种过程。更严格的讲，算法是由若干条指令组成的有穷序列。
算法具有以下四种性质：
1.输入：有零个或多个由外部提供的量作为算法的输入。
输入是为了让算法有能够进行处理的原始数据，如果没有输入，算法对什么进行操作呢？所以要有输入。
2.输出：算法产生至少一个量作为输出。
如果没有输出的话，如何能够知道算法是否正确的产生了我们所预期的结果？如何能够知道算法是否正确的解
决了预期要解决的问题呢？
3.确定性 ：组成算法的每一条指令是清晰的，无歧义的。
如果每一条指令不是清晰的，无歧义的，那么在解决问题的时候如何能够保证算法对于同样的输入能够产生同
样的结果呢？这样也就无法保证算法对输入能够正确的进行处理。
4.有限性：算法中每条指令执行的次数是有限的，执行每条指令的时间也是有限的。
一个算法的时间可以由下式进行求解$T_总 = \sum_{i=1}^nT_i$其中$T_i$表示第i条指令的执行时间，
如果执行每条指令的时间不是有限的，就会导致$T_总$是无限的，如果每条指令执行的次数不是有限的，会导
致n为$\infty$从而执行的时间是无限的，如果一个算法的执行时间是无限的，这就代表算法要产生结果的时间
是无限的，也就是说我们永远无法得到该算法的结果，更不要说验证算法是否正确了。
程序和算法不同，程序是算法的具体实现，程序可以不满足算法的性质4，如操作系统是在一个无限循环中执行的程序。
1.2算法复杂性
算法复杂性 { 时间复杂性 从时间角度来看 空间复杂性 从空间角度来看 算法复杂性\begin{cases}时间复杂性 & 从时间角度来看\\ 空间复杂性 & 从空间角度来看 \end{cases} 算法复杂性{时间复杂性空间复杂性从时间角度来看从空间角度来看
算法的复杂性是一个算法所需资源的多少的一个度量，需要进行算法复杂性分析的原因是因为时间资源和空间资源是有限的，为了能更高效的办成事，算法复杂性更像一个评价指标推动我们对算法进行优化。
因为算法的复杂性是一个算法所需资源的一个度量，算法所需的资源依赖于算法要解决的问题的规模，算法的输入和算法本身，分别使用N、I、A来代替可知 C = F ( N , I , A ) C = F(N, I, A) C=F(N,I,A),如果我们只从时间的角度进行考虑时间复杂性则可得 T = T ( N , I , A ) T = T(N, I, A) T=T(N,I,A)同理可得空间复杂性 S = S ( N , I , A ) S = S(N, I, A) S=S(N,I,A),因为A是与算法本身有关的一个量，所以可以对上述公式进行简化得 T = T ( N , I ) T = T(N, I) T=T(N,I) S = S ( N , I ) S = S(N, I) S=S(N,I)。
1.2.1算法的时间复杂性
如果要得到一个算法的运行时间，就需要对算法在具体的机器上进行运行，这样能够得到该算法在此机器上的运行时间，但是这不具有普遍性，在这一台电脑上运行时间是这样，那换另一台电脑还是这样吗？所以为了保证为我们的分析具有普遍性，需要将算法的时间复杂性同具体的电脑分离开，所以据需要抽象。我们在一台假想的理想计算机上运行算法，这台计算机提供n种指令，执行每种指令都只需要常量时间 t 1 , t 2 , . . . . . . , t n t_1,t_2,......,t_n t1,t2,......,tn，对于相同的指令，执行需要相同的时间，一个算法执行第k条指令的次数 e k e _k ek为关于问题规模N和算法输入I的量,即 e k = e k ( N , I ) e_k = e_k(N, I) ek=ek(N,I)，又第k条指令执行的时间为t_k所以时间复杂性可以表示为 T = ∑ i = 1 n t i e i ( N , I ) T=\sum_{i=1}^{n}t_ie_i(N, I) T=∑i=1ntiei(N,I)
1.3NP完全性理论
问题分为P类问题（多项式问题：可以在多项式时间内进行解决）和NP类问题（非确定性多项式问题：它们的解决方法尚未被找到多项式时间内解决的算法，但如果给定一个解，可以在多项式时间内验证该解的正确性。）
NP完全问题（即NPC类问题）：这类问题具有一种性质，如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每个问题都可以在多项式时间内求解，即P=NP。