算法（algorithm）是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。对于一个问题，一旦给定某种算法并且（以某种方式）确定其是正确的，那么重要的一步就是确定该算法将需要多少诸如时间或空间等资源量的问题。
定义：如果存在正常数c和n_0 使得当N ≥ n_0 时T(N) ≤ cf(N)，则记为T(N)= O(f(N))。
定义：如果存在正常数c和n_0 使得当N ≥ n_0 时T(N) ≥ cg(N)，则记为T(N) = Ω(g(N))。
定义：如果T(N) = O(h(N))且T(N) = Ω(h(N))，则记为T(N) = Θ(h(N))。
定义：如果T(N) = O(p(N))且T(N) ≠ Θ(p(N))，则记为T(N) = o(p(N))。
这些定义的目的是要在函数间建立一种相对的级别。给定两个函数，通常存在一些点，在这些点上一个函数的值小于另一个函数的值，因此，像f(N) < g(N)这样的声明没有什么意义的。于是，我们比较它们的相对增长率。那么第一个定义是说T(N)的增长率小于定于f(N)的增长率。第二个定义T(N)=Ω(g(N))是说T(N)的增长率大于等于g(N)的增长率。第三个定义T(N)=Θ(h(N))是说T(N)的增长率等于h(N)的增长率。最后一个定义T(N)=o(p(N))说的则是T(N的增长率小于p(N)的增长率。它不同于大O，因为大O包含增长率相同这种可能性。
法则1:
如果T_1 (N) = O(f(N))且T_2 (N) = O(g(N))，那么
(a) T_1 (N) + T_2 (N) = max(O(f(N)), O(g(N)))，
(b) T_1 (N) * T_2 (N) = O(f(N)*g(N))。
法则2:
如果T(N) 是一个k次多项式，则T(N) = Θ(N^k)。
法则3:
对任意常数k，log^k N = O(N)。它告诉我们对数增长得非常缓慢。
典型的增长率
| 函数 | 名称 |
|---|---|
| c | 常数 |
| logN | 对数级 |
| log^2 N | 对数平方根 |
| N | 线性级 |
| NlogN | |
| N^2 | 平方级 |
| N^3 | 立方级 |
| 2^N | 指数级 |
为了在正式的框架中分析算法，我们需要一个计算模型。我们的模型基本是一台标准的计算机，在机器中指令被顺序地执行。该模型有一个标准的简单指令系统，如加法、乘法、比较和赋值等。
要分析的最重要的资源一般来说就是运行时间。有几个因素影响着程序的运行时间。典型的情形是，输入的大小是主要的考虑方面。一般来说，若无相反的指定，则所需要的量是最坏情况下的运行时间。
法则1 – FOR循环
一次for循环的运行时间至多是该for循环内语句（包括测试）的运行时间乘以迭代的次数。
法则2 – 嵌套的for循环
从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的for循环的大小的乘积。
法则3 – 顺序语句
将各个语句的运行时间求和即可（这意味着，其中的最大值就是所得的运行时间）
法则4 – IF/ELSE
一个if/else语句的运行时间从不超过判断再加上各个语句块中运行时间长的总的运行时间。
显然在某些情形下这么估计有些过高，但绝不会估计过低。
其他的法则都是显然的，但是，分析的基本策略是从内部（或最深层部分）向外展开的。
- 穷举法（N^3 和 N^2 两种（通过避免for循环避免立方运行时间））
- 分冶法，把问题分成两个大致相等的子问题，然后递归地对它们求解，这是“分”部分。“冶”阶段将两个子问题的解合并到一起，并可能再做些少量的附加工作，最后得到这个问题的解
- 滑动法，只对数据进行一次扫描
滑动法示例
int
MaxSubsequenceSum(const int A[], int N)
{
int ThisSum,MaxSum,j;
ThisSum = MaxSum = 0;
for(j = 0; j < N; j++){
ThisSum += A[j];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
else
ThisSum = 0;
}
return MaxSum;
}分析算法最混乱的方面大概集中在对数上面。某些分冶算法将以O(NlogN)时间运行。除分冶算法外，可将对数最长出现的规律概括为下列一般法则： 如果一个算法用常数时间(O(1)将问题的大小削减为其某一部分（通常是1/2），那么该算法O(logN))。另一方面，如果使用常数时间只是把问题减少一个常数（如将问题减少1），那么这边算法就是O（N）的。
对分查找
int
BinarySearch(const ElementType A[], ElementType X, int N)
{
int Low,Mid,Hih;
Low = 0;High = N - 1;
while( Low <= High)
{
Mid = ( Low +High) / 2;
if( A[Mid] < X)
Low = Mid + 1;
else
if( A[Mid] > X)
High = Mid - 1;
else
return Mid;
}
return NotFound;
}欧几里德算法
两个整数的最大公因数（Gcd）是同时整除二者的最大整数；
unsigned int
Gcd( unsigned int M, unsigned int N)
{
unsigned int Rem;
while( N > 0)
{
Rem = M % N;
M = N;
N = Rem;
}
return M;
}幂运算
long int
Pow( long int X, unsigned int N)
{
if(N == 0)
return 1;
if(N == 1)
return X;
if(IsEven(N))
return Pow(X*X,N/2);
else
return Pow(X*X,N/2)*X;
}例如，为了计算X^62 ,算法将如下进行，它只用到9次乘法：
X^3 = (X^2)X,X^7 = (X^3)^2 X,X^15 = (X^7)^2 X,X^31 = (X^15)^2 X,X^62 = (X^31)^2
本文对如何分析程序的复杂性给出来一些提示。遗憾的是，它并不是完善的分析指南。简单的程序通常给出简单的分析，但是情况也并不是总是如此。例如希尔排序，不过，我们遇到的大部分的分析都是简单的，它们涉及到对循环的计数。