1.2 算法的指标——空间复杂度和时间复杂度

1.1.3节中留了个问题，同一个算法通过不同的程序都可以实现，那么如何评价算法是好是坏呢？一个算法如果要运行1000年，那么这个算法肯定不是好算法；如果一个算法要占用整个计算机内存，那么这个算法肯定也不是好算法。一个好的算法要求运行时间尽可能的短，占用的空间尽可能的少。当然，由于现在计算机技术的飞速发展，其运算速率越来越高，存储越来越大，人们对算法的运行时间和占用空间要求越来越低，反而对程序的健壮性和可维护性等要求比较高。但是一些嵌入式设备，如手表，内存很小，因此其对算法的性能要求是非常高的，运行时间和占用空间都会受到严格限制。我们通常通过时间复杂度来衡量算法的运行时间，通过空间复杂度来衡量算法的占用空间。

（1）时间复杂度：算法运行需要的时间，我们一般用算法的执行次数进行表示。

（2）空间复杂度：算法运行需要的内存空间，我们一般使用算法在运行过程中开辟的空间进行表示。

如果一个算法的时间复杂度和空间复杂度都很小，那么这个算法无疑是一个非常优秀的算法，但是这种算法少之又少。通常我们会在时间复杂度和空间复杂度之间进行取舍，以时间换空间，或以空间换时间。

算法复杂度分为时间复杂度和空间复杂度，当然我们可以通过运行一遍程序直接统计算法的运行时间和占用内存，但是这个方法存在很大的弊端，因为我们在考虑算法的时候，还没有办法完整地运行程序。所以我们需要一种通过理论分析算法复杂度的方法——大O表示法。大O表示法因使用符号大O而得名。