算法复杂度及渐进符号

一、算法复杂度

首先每个程序运行过程中，都要占用一定的计算机资源，比如内存，磁盘等，这些是空间，计算过程中需要判断，循环执行某些逻辑，周而反复，这些是时间。

那么一个算法有多好，多快，怎么衡量一个算法的好坏？所以，计算机科学在算法分析过程中，提出了算法复杂度理论，这套理论可以量化算法的效率，以此作为标准，方便我们能衡量到底选择哪一种算法。

复杂度有两个维度：时间和空间。

我们说，一个实现了某算法的程序：

  1. 如果计算的速度越快，那么这个算法时间复杂度越低。
  2. 如果占用的计算资源越少，那么空间复杂度越低。

我们要选择复杂度低的算法，衡量好空间和时间的消耗，选出适合特定场景的算法。

这两个复杂度维度的量化过程都是一样的，所以我们这里主要介绍时间复杂度。

二、算法规模

1 + 2 + 3 + ... + 100
n = 10n-1nn
问题规模 n
n-1nO(n)

我们有另外一种计算方式：

1O(1)O(1)O(n)

当然，还有指数级别的比如之前的汉诺塔算法，对数级别的，阶乘级别的复杂度ÿ