分类： C/C++
2010-07-22 16:36:39
白话算法复杂度
很多CSDN学生大本营的同学都学了《数据结构》这门课，我从我的《J2EE开发全程实录》中摘取了下面的片段，希望对大家有帮助。
计算机中最核心的资源就是CPU与存储器，任何程序的运行都离不开二者。任何程序的运行都要进行计算，这就会消耗CPU；任何程序的运行也都需要进行数据的处理，CPU中是无法存储数据的，必须借助存储器来保存数据。如果程序的CPU消耗过大的话就会导致程序的运行时间变长；如果占用的存储空间太大的话就会使得系统能够运行的程序数量变少。因此如何保证程序占用的CPU和占用的存储空间都较小就成了我们研究的一个重点，任何系统的调优也都是以此为目标的。
通俗的讲，一个算法的空间消耗指的是这个算法运行所需要的存储空间大小，而时间消耗指的是算法运行所需要的时间。一个算法运行时所消耗的空间与时间通常与运行环境有关，同一个算法在配置不同的计算机上运行的时间消耗和空间消耗也不同。比如对于一个存储空间需求极大的算法，如果可用的存储空间不够，在运行的时候就要频繁的进行内外存的交换，这样需要运行的时间就会变长；可用空间足够大，但是 CPU运行速度较慢的话，就会导致算法占据存储空间的时间变长，从而导致占用的存储空间的总体值上升，必须找到一种不依赖于软硬件条件的对空间与时间进行度量的方法。因为算法的复杂性与具体的运行环境无关，所以通过比较算法的复杂性来评价算法是比较合理的。
算法的复杂性分为空间复杂度和时间复杂度。空间复杂度是指当问题的规模以某种单位从1增加 到n时，解决这个问题的算法在执行时间所占用的存储空间也以某种单位从1增加到f(n)，那么就称此算法的空间复杂度为f(n)；时间复杂度是指当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时间所消耗的时间也以某种单位从1增加到f(n)，那么就称此算法的时间复杂度为g(n)。空间 单位一般规定为一个工作单元所占用的存储空间的大小，时间单位一半规定为一个程序步。
我们需要一种方式来把空间复杂度和时间复杂度的度量弄的更精确一些，人们提出了一种标准的记法，被称为“大O记 法”。在这种记法中使用的基本参数是n，也就是问题的规模，把复杂度表示为n的函数。这里的“O”是英文“Order”的缩写，此处的“Order”不是 “顺序”的意思，而是代表“数量级”。比如说“数组遍历是O(n)的”，意思就是说“通过O(n)量级的步骤去遍历一个数组”。
我们总是追求程序通过占用最少的存储空间以最快的速度(即最少的CPU时间占用)来完成任 务，但是这两者常常是此消彼涨的：当一个程序改进到能够占用更少存储空间的时候，它消耗的CPU时间就会增加；当一个程序改进到占用较少的CPU时间的时 候，它占用的存储空间通常又会上升。
比如，计算高精度的PI值是非常消耗系统CPU时间的，而其占用的存储空间则相对较小。为
了防止每次计算都消耗漫长的CPU时间，可以在一次计算以后把计算结果保存到存储器中，这样下次计算的时候直接从存储器中读取就可以了，这样占用的CPU 时间就非常短了，但是占据的存储空间就增加了。
数据库的索引也是一个明显的例子。为了提高数据检索的速度，常常需要对数据表的字段建立索引，这样就可以用更少的CPU消耗来检索到需要的数据了，但索引是要占据存储空间，这就导致了存储空间的上升。
既然空间与时间的占用存在着这种背反性，那么必须在空间与时间的优化上找到一个平衡点。现代的计算机的存储器容量非常大，而且价格也非常低廉，而CPU则属于比较宝贵的资源，所以现代的程序设计更多的是以空间换取时间，也就是用较高的存储空间占用来换取较少的CPU时间。
以空间换时间的例子是非常多的。
【实例2-1】阶乘计算
本实例给定一个整数n(n大于等于0，小于等于10)，计算它的阶乘值。
算法1：
代码 2.1 普通的阶乘计算
public class JCCalc01
{
public static void main(String[]
args)
{
for (int
i = 0, n = 10; i < n; i++)
System.out.println(calcFactor(i));
}
private static int
calcFactor(int value)
{
if
(value < 0 || value > 10)
{
throw new IllegalArgumentException();
}
if
(value == 0)
{
return 1;
} else
{
return calcFactor(value - 1) * value;
}
}
}
算法2：
代码2.2 优化的阶乘计算
public class JCCalc02
{
private static int[] FACTORARRAY
= new int[]{1,1,2,6,24,120,720,5040,40320,362880};
public static void main(String[]
args)
{
System.out.println(calcFactor(10));
}
private static int
calcFactor(int month)
{
return
FACTORARRAY[month-1];
}
}
算法1是最常见的写法，我们从开始学编程的时候老师就是这么教的，但是由于递归调用是非常 消耗时间的，因此算法1的时间复杂度也是非常高的；而算法2则相对来说“土”了一些，它把计算结果已经预先计算出来的，当使用的时候只要按照下标去取就可
以了，虽然FACTORARRAY 数组会占用一定存储空间但是给程序运行速度带来的提高还是很明显的。
再来看一个问题：
程序随机给出10000个10000以内的整数n，请计算它们的阶乘。
由于这里边的变量n的取值范围大了很多，所以不可能像第一个问题那样预先计算并写在程序中了，为此最初的想法就是即时计算了。
算法1：
代码 2.3 普通的大数阶乘计算
public class JCCalc03
{
public static void main(String[]
args)
{
Random
random = new Random();
for (int
i = 0; i < 10000; i++)
{
int randInt = random.nextInt(10000);
System.out.println(calcFactor(BigInteger.valueOf(randInt)));
}
}
private static BigInteger
calcFactor(BigInteger value)
{
if
(value.compareTo(BigInteger.valueOf(0)) == 0)
{
return BigInteger.valueOf(1);
} else
{
BigInteger nPlusOne = value.subtract(BigInteger.valueOf(1));
return calcFactor(nPlusOne).multiply(value);
}
}
}
由于阶乘曲线增长速度非常快，当n取值稍大的时候计算结果就已经超出了int、long等Java基本类型的范围了，所以使用java.math包中的BigInteger类来进行超长数据的阶乘运算。
运行以后发现程序的速度非常慢，这是可以理解的，BigInteger的四则运算是比 Java原始类型的计算慢很多倍的，更重要的，每次计算n的阶乘的时候，都要进行递归运行来计算1*2*3……*(n-1)*n，当n过大的时候还会造成 StackOverFlow的问题。
我们来考虑如果进行优化：在计算100的阶乘的时候如果99的阶乘已经计算过了，那么只要把99的阶乘的结果乘以100就可以了，无需从1开始乘起，这样优化的重点就是把计算的结果缓存起来。
在Java中进行缓存操作有一个非常有用的工具，那就是java.util.Map接口，
它有HashMap、HashTable等几个实现类。我们把数据按照某个唯一的值做为键插入这个接口的某个变量中，以后只要按照键为参数就可以将数据取
出来，而且近似的可以认为按照键取数据的这个过程不需要时间。
基于这个快速按照键取数据的这个特性，我们就可以把Map当作一个缓存使用，将计算完成的阶乘结果按照n为键、n的阶乘为值进行缓存。
算法2：
代码 2.4 优化后的大数阶乘计算
public class JCCalc04
{
private static Map map = new
HashMap(10000);
public static void main(String[]
args)
{
Random
random = new Random();
for (int
i = 0; i < 10000; i++)
{
int randInt = random.nextInt(10000);
System.out.println(calcFactor(BigInteger.valueOf(randInt)));
}
}
private static BigInteger
calcFactor(BigInteger value)
{
if
(value.compareTo(BigInteger.valueOf(0)) == 0)
{
return BigInteger.valueOf(1);
} else
{
//从缓存中查找value的阶乘
BigInteger factor = (BigInteger) map.get(value);
if (factor != null)
{
//如果查找到了则直接返回缓存中的阶乘值
return factor;
}
BigInteger nPlusOne = value.subtract(BigInteger.valueOf(1));
factor = calcFactor(nPlusOne).multiply(value);
map.put(value, factor);
return factor;
}
}
}
可以看到程序的运行速度快了不少。合理的使用缓存将会大大提升系统的性能。这里强调合理二字的意义就在于，缓存在减小了系统的时间占用的同时，也提高了系统的存储空间占用，虽然存储空间不像CPU资源那样宝贵，但是毕竟其资源也是有限的，不能无止境的耗用，所以就需要采用淘汰算法等来限制缓存的资源占用。
