前言

俗话说，“语言只是工具，算法才是程序的灵魂”。对于程序员来说，算法始终是一个绕不开的门槛。近两年，越来越多的互联网公司在招聘环节注重算法的考察。

什么是好的算法？

我们通常有下面两个指标：

• 空间复杂度：根据算法写成的程序在执行时占用存储单元的长度。
• 时间复杂度：根据算法写成的程序在执行时耗费时间的长度。

在实践中或面试中，我们不仅要能够写出具体的算法来，还要了解算法的时间复杂度和空间复杂度，这样才能够评估出算法的优劣。当时间复杂度和空间复杂度无法同时满足时，还需要从中选取一个平衡点。

如何计算时间复杂度？

常见的时间复杂度量级有：

• 常数阶O(1)
• 对数阶O(logN)
• 线性阶O(n)
• 线性对数阶O(nlogN)
• 平方阶O(n2)
• 立方阶O(n3)
• 指数阶(2^n、n!、n^n)

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。优劣排序如下：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)< O(2^n) < O(n!) < O(n^n)

求解算法复杂度一般分以下几个步骤：

• 找出算法中的基本语句：算法中执行次数最多的语句就是基本语句，通常是最内层循环的循环体。
• 计算基本语句的执行次数的数量级：只需计算基本语句执行次数的数量级，即只要保证函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，使注意力集中在最重要的一点上：增长率。
• 用大Ο表示算法的时间性能：将基本语句执行次数的数量级放入大Ο记号中。

其中用大O表示法通常有三种规则：

• 用常数1取代运行时间中的所有加法常数；
• 只保留时间函数中的最高阶项；
• 如果最高阶项存在，则省去最高阶项前面的系数；

下面通过具体的实例来说明以上的推算步骤和规则：

（1） 常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

int i = 1;
int j = 2;
++i;
j++;
int k = i + j;

上述代码执行时，单个语句的频度均为1，不会随着问题规模n的变化而变化。因此，算法时间复杂度为常数阶，记作T(n)=O(1)。这里我们需要注意的是，即便上述代码有成千上万行，只要执行算法的时间不会随着问题规模n的增长而增长，那么执行时间只不过是一个比较大的常数而已。此类算法的时间复杂度均为O(1)。

（2）对数阶O(log n)

int i = 1; // ①
while (i <= n) {
   i = i * 2; // ②
}

在上述代码中，语句①的频度为1，可以忽略不计。

语句②我们可以看到它是以2的倍数来逼近n，每次都乘以2。如果用公式表示就是1*2*2*2…*2 <=n，也就是说2的x次方小于等于n时会执行循环体，记作2^x <= n，于是得出x<=logn。也就是说上述循环在执行logn次之后，便结束了，因此上述代码的时间复杂度为O(log n)。

其实上面代码的时间复杂度公式如果精确的来讲应该是：T(n) = 1 + O(log n)，但我们上面已经讲到对应的原则，“只保留时间函数中的最高阶项”，因此记作O(log n)。

（3）线性阶O(n)

int j = 0; // ①
for (int i = 0; i < n; i++) { // ②
   j = i; // ③
   j++; // ④
}

上述代码中，语句①的频度为1，②的频度为n，③的频度为n-1，④的频度为n-1，因此整个算法可以用公式T(n)=1+n+(n-1)+(n-1)来表示。进而可以推到T(n)=1+n+(n-1)+(n-1)=3n-1，即O(n)=3n-1，去掉低次幂和系数即O(n)=n，因此T(n)=O(n)。

在上述代码中for循环中的代码会执行n遍，因此它消耗的时间是随着n的变化而成线性变化的，因此这类算法都可以用O(n)来表示时间复杂度。

（4）线性对数阶O(nlogN)

for (int m = 1; m < n; m++) {
   int i = 1; // ①
   while (i <= n) {
      i = i * 2; // ②
   }
}

线性对数阶要对照对数阶 O(log n)来进行理解。上述代码中for循环内部的代码便是上面讲到对数阶，只不过在对数阶的外面套了一个n次的循环，当然，它的时间复杂度就是n*O(log n)了，于是记作O(nlog n)。

（5）平方阶O(n2)

int k = 0;
for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
      k++;
   }
}

平方阶可对照线性阶来进行理解，我们知道线性阶是一层for循环，记作O(n)，此时等于又嵌套了一层for循环，那么便是n * O(n)，也就是O(n * n)，即O(n^2)。

（6）立方阶O(n3)

int a = 0;
for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        a++;
     }
   }
}

同理，立方阶O(n3)相对于平方阶O(n2)，只不过是多嵌套了1层循环而已。那么便是n * O(n*n)，也就是O(n * n * n)，即O(n^3)。

（6）指数阶O(2^n)

int Fibonacci(int number)
{
    if (number <= 1) return number;
    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

O(2^n)，表示一个算法的性能会随着输入数据的每次增加而增大两倍，典型的方法就是上述代码中裴波那契数列的递归计算的实现。

严格来说，斐波那契数列的时间复杂度的紧界不是 O(2^n)，而是O(((1+√5）/ 2)^n)，有兴趣的同学可以自己推导一下～

如何计算空间复杂度？

程序执行除了需要存储空间、指令、常数、变量和输入数据外，还包括对数据进行操作的工作单元和存储计算所需信息的辅助空间。存储空间通常包括：指令空间（即代码空间）、数据空间（常量、简单变量）等所占的固定部分和动态分配、递归栈所需的可变空间。其中可变空间与算法有关。

一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))其中n为问题的规模，S(n)表示空间复杂度。

下面看两个常见的空间复杂度示例：空间复杂度O(1)和O(n)：

（1）空间复杂度 O(1)

int i = 1;
int j = 2;
int k = i + j;

上述代码中临时空间并不会随着n的变化而变化，因此空间复杂度为O(1)。

总结一下就是：如果算法执行所需要的临时空间不随着某个变量n的大小而变化，此算法空间复杂度为一个常量，可表示为 O(1)，即 S(n) = O(1)。

（2）空间复杂度 O(n)

int j = 0;
int[] m = new int[n];
for (int i = 1; i <= n; ++i) {
   j = i;
   j++;
}

上述代码中，只有创建int数组分配空间时与n的大小有关，而for循环内没有再分配新的空间，因此，对应的空间复杂度为S(n) = O(n)。