首先接触" 算法复杂度"这个术语是在数据结构这门课程中。数据结构主要是讲如何在计算机中存储.组织数据，对于相同的存储.组织数据方式，往往又有不同的实现方式(即算法)。对于精心实现的算法，往往可以带来更高的运行和存储上的效率，而评价一个实现方式(算法)是否高效就是通过" 算法复杂度"来评定的。目前算法的评定主要是从时间和空间上来评定，毕竟我们对计算机关心的一个是运行时间，另一个就是消耗的存储空间。从时间上评定算法的优劣称为"时间复杂度"，自然，从空间上评定算法的优劣就称为"空间复杂度"。
一.时间复杂度:
一个算法执行所用的时间，理论上讲是不能通过计算得出来的，因为它受多方面的影响，比如说不同的硬件，相同的算法在不同的硬件机器上执行，所消耗的时间是不同的。即使是在同一台机器上，一个算法在不同的时间执行，所消耗的时间也是不同的(当某个时刻计算机系统待处理的任务比较多时，这个时刻算法执行消耗的时间相对于计算机系统待处理任务较少时，所用的时间可能会多些)。我们使用"时间复杂度"并不是为了计算算法执行所消耗的时间，而是用于评定不同的算法之间在时间成本上，那个消耗的时间理论上少些，那个多些。背后的原理是这样的:如果有两个算法A,B，假如它们实现的功能都是在一个相同长度的数组内查找符合条件的一个元素位置。经过"时间复杂度"的评定，算法A在时间成本上比算法B消耗的时间要少。那么在实际运行中算法A的执行应该会比算法B快。请注意我使用了"应该"这个词语，毕竟任何情况都有特殊的时候，不是吗？但毕竟特殊的情况属于少数，大多数情况下还是正常的。所以请不要认为"算法复杂度"是属于理论的东西，没有什么实际的意义。它在评定算法优劣上占有非常重要的地位。
讨论时间复杂度时，不得依次说明下面几个术语所表达的意思，当对这些术语背后表达的意思明白过后，"时间复杂度"也自然而然的明白了。
1.算法消耗时间.
一个算法执行所消耗的时间 = 算法中所有语句执行的时间之和。
如果我们独立机器的软，硬件。假定语句执行一次所消耗的时间一样，并把语句执行一次所消耗的时间定义为单位时间。这样的假定有助于我们理解，并能把问题集中在需要考虑的地方。
2.语句频度.
语句频度是指算法中语句的执行次数.
那么算法中每条语句的执行时间 ＝ 该语句的执行次数(语句频度)*单位时间
所以一个算法执行所消耗的时间 = 算法中所有语句的语句频度*单位时间
例:
求两个n阶方阵C=A*B的乘积其算法如下:
//右边列为语句执行的频度
void MatrixMultiply(int A[n][n]，int B [n][n]，int C[n][n])
{
(1) for(int i=0; i <n; i++) //n+1
{
(2) for (j=0;j < n; j++) //n*(n+1)
{
(3) C[i][j]=0; //n2
(4) for (k=0; k ,n; k++) //n2*(n+1)
{
(5) C[i][j]=C[i][j]+A[i][k]*B[k][j]; //n3
}
}
}
}
则该算法所有语句的频度之和为:
T(n) = 2n3+3n2+2n+1;
算法执行时间:
T(n)*单位时间，设单位时间为1.则算法执行时间 ＝ T(n)
可以看出算法MatrixMultiply的执行时间T(n)是一个关于矩阵阶数n的函数
3.问题规模
在上面的算法执行时间T(n)是一个关于n的函数，n称为"问题规模"."问题规模"(这里是n)与算法的执行次数有关，在上面的例子中，n越大，算法的执行次数越多。当然也会存在某个算法的执行次数与"问题规模"无关的情况.比如说下面的函数:
void AddTenTimes( int& a )
{
for( int i=0; i<=10; i++ ) //11
{
++a; //10
}
}
T(n) = 21;为一个常数
4.渐进时间复杂度
还是接着算法MatrixMultiply例子说，上面我们求出了，该算法的语句频度:T(n) = 2n3+3n2+2n+1;如果我们能找到一个函数f(n),使当n趋于无穷大时，T(n)/f(n)的极限值为一个不等于零的常数，则称f(n)是T(n)的同数量级函数.并记T(n)=O(f(n))为算法的渐进时间复杂度。注:这里多了一个符号O,符号O只是一个标识，它并不代表任何的数学运算。在上面的例子中我们能很容易的找到f(n) = n3.
这里的渐进时间复杂度，即是我们常说的时间复杂度。
5.常见的时间复杂度
按数量级递增的排列，常见的依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/zengwke/archive/2008/05/17/2454624.aspx