定义1：算法是进行一项计算或解决一个问题的准确指令的优先序列。
算法的性质：
停机问题(halting problem)：它询问是否存在一个过程（procedure）能做这件事：该过程以一个计算机程序以及该程序的一个输入作为输入，并判断该程序在给定输入运行时是否最终能停止。
证 假设停机问题有一个解，一个称为H(P,I)的过程。过程H(P,I)有两个输入项，一个是程序P，另一个是程序P的一个输入I。如果H判定P在给定输入I时能终止，则H(P,I)将产生字符串“停机”作为输出。反之，H(P,I)将产生字符串“无限循环”作为输出。现在我们将导出一个矛盾。
为了证明不存在过程H能够求解停机问题，我们构造一个简单过程K(P)，它的工作原理如下，并利用H(P,P)的输出。如果H(P,P)的输出是“无限循环”，即P在自身作为输入时会无限循环，那么让K(P)停机。如果H(P,P)的输出是“停机”，即P在自身作为输入时会停机，那么让K(P)无限循环。即，K(P)做出和H(P,P)的输出相反结果（如图2所示）。
现在假设把K作为K的输入。需要注意，如果H(K,K)的输出是“无限循环”，那么根据K的定义可以得出K(K)停机。否则，如果H(K,K)的输出是“停机”，那么根据K的定义K(K)会无限循环，而这与H给出的结果是相违背的。在这两种情况下，都会产生矛盾。
定义1：令f和g为从整数集或实数集到实数集的函数。如果存在常数C和k使得只要当x>k时就有 $|f(x)| \le C|g(x)|$，我们就说f(x)是O(g(x))的。读作“f(x)是大Og(x)的”。
评注：直觉上，f(x)是O(g(x))的定义是说当x无限增长时f(x)的增长慢于g(x)的某个固定的倍数。
定理1：令$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$，其中$a_0,a_1,\cdots,a_{n-1},a_n$为实数。那么f(x)是$O(x^n)$的。
大O符号可以用来估计用一个特定的计算机过程或算法解题时所需要的操作步数。用于估计的常用函数包括：$1,logn,n,nlogn,n^2,2^n,n!$
定理2：假定f1(x)是O(g1(x))的，f2(x)是O(g2(x))的，那么(f1+f2)(x)是O(max(|g1(x)|,|g2(x)|))的。
推论1：假定f1(x)和f2(x)都是O(g(x))的，那么(f1+f2)(x)也是O(g(x))的。
定理3：假定f1(x)是O(g1(x))的，f2(x)是O(g2(x))的，那么(f1f2)(x)是O(g1(x)g2(x))的。
定义2：令f和g为从整数集或实数集到实数集的函数。如果存在常数C和k使得只要当x>k时就有 $|f(x)| \ge C|g(x)|$，我们就说f(x)是$\Omega(g(x))$的。读作“f(x)是大$\Omega(g(x))$的”。
定义3：令f和g为从整数集合或实数集合到实数集合的函数。如果f(x)是O(g(x))的且f(x)是$\Omega(g(x))$的，我们就说f(x)是$\Theta(g(x))$。当f(x)是$\Theta(g(x))$时就说f(x)是大西塔g(x)的，即f(x)是g(x)阶的，或f(x)和g(x)是同阶的。
定理4：令$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$，其中$a_0,a_1,\cdots,a_{n-1},a_n$为实数且$a_n \ne 0$。则f(x)是$x^n$阶的。
计算复杂度：解决特定规模的问题所需时间的分析就是算法的时间复杂度。所需计算机内存的分析就是算法的空间复杂度。
最坏情形复杂度：所谓一个算法的最坏情形性能，指的是该算法用于具有一定输入规模的问题时所需要的最多的运算次数。最坏情形分析告诉我们一个算法需要多少次运算就能保证给出问题的解答。
平均情形复杂度：在这类分析中就是要找出求解针对一定规模的问题的所有可能得输入所用到的运算的平均数。平均情形时间复杂度分析一般比最坏情形分析复杂得多。
在蛮力算法（brute-force algorithm）中，问题是通过基于对问题的描述和术语的定义以最直接的方式解决的。
一类重要的问题，称为NP完全问题（NP-complete problem），具有这样的性质即只要其中任何一个问题能用一个多项式时间最坏情形算法来求解，那么NP类的所有问题都能用多项式时间最坏情形算法来求解。可满足性问题就是NP完全问题的一个例子。它是一个NP问题，并且如果知道了一个求解它的多项式时间算法，那么所有已知在该问题类中的所有问题就都有多项式时间算法（在这个类中有许多重要问题）。最后这个叙述基于这样一个事实，即NP中的每个问题可在多项式时间内归约为可满足性问题。
P与NP问题（P versus NP problem）：是问NP（有可能在多项式时间内检验其解的一类问题）是否等于P（一类易解的问题）。如果$P \ne NP$，则存在这样一些不能在多项式时间内求解但其解可以在多项式时间内验证的问题。
表2给出用算法求解各种输入规模问题所需的时间，这里用位运算的位数n表示，并假定每次位运算需要的时间是$10^{-11}$秒，这是以今天最快的计算机做位运算所需时间的一种合理估计。需要的时间超过$10^{1000}$年的在表中用星号表示。
In [ ]: