前言

算法是指一组用于操纵数据和解决程序问题的方法。算法是大厂、外企面试必备的项目，也是每个资深程序员必备的技能。解决同一个问题的算法有很多，但是不同的算法在效率和存储空间上可能有很大的差异。

那么，用什么指标来衡量算法的优劣呢？其中，上面提到的效率可以用算法的时间复杂度来描述，占用的存储空间可以用算法的空间复杂度来描述。

时间复杂度：用于评估执行程序所消耗的时间，可以估计程序对处理器的使用程度。空间复杂度：用于评估执行程序占用的内存空间，可以估计程序对计算机内存的使用情况。在实践或面试中，我们不仅要能写出具体的算法，还要知道算法的时间复杂度和空间复杂度，从而评价算法的优劣。当时间复杂度和空间复杂度不能同时满足时，需要选择一个平衡点。

一个算法通常有最好的、平均的和最坏的情况，我们一般关注最坏的情况。最坏的情况是算法运行时间的上限。对于一些算法来说，最坏的情况经常发生，这也意味着平均情况和最坏的情况一样糟糕。

通常时间复杂度比空间复杂度更容易出现问题，更多的研究是时间复杂度。如果面试中没有特别说明，也是关于时间复杂度的。

00-1010要得到算法的时间复杂度，最直观的想法就是运行一次算法程序，自然就能得到。但在实践中，往往受到测试环境、数据规模等因素的限制。直接测试算法要么难以实现，要么误差较大。理论上，没有必要对每个算法测试一次。只需要找到一个评价指标，得到算法执行时间的基本趋势。

时间复杂度

通常，算法花费的时间与执行的代码语句的数量成正比。算法执行的语句越多，消耗的时间就越多。我们称语句的执行次数为算法时间频率，并记录为T(n)。

00-1010在时间频率T(n)中，n代表问题的规模。当n不断变化时，T(n)也会不断变化。那么，如果我们想知道T(n)随n变化时会表现出什么规律，那么就需要引入时间复杂度的概念。

一般来说，算法基本运算的重复次数是问题大小n的函数，即用时间频率T(n)表示。如果存在某个函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不为零的常数，那么f(n)就是与T(n)同量级的函数，表示为T(n)=O(f(n))，O(f(n)称为算法的渐近性。

渐进时间复杂度用大写O表示，所以也叫大O记数法。算法的时间复杂度函数为：t(n)=o(f(n))；

T(n)=O(f(n))意味着有一个常数C，所以当n趋近于正无穷大时，总有T(n) C * f(n)。简单来说就是当n趋于正无穷大时，T(n)和f(n)一样大。也就是说，当n趋于正无穷大时，T(n)的上界为C * f(n)。虽然对f(n)没有规定，但一般是尽可能简单的函数。

常见的时间复杂度有：O(1)常数型；O(log n)对数型、O(n)线性型、O(nlog n)线性对数型、O(n2)平方型、O(n3)立方型、O(nk)k幂型和O(2n)指数型。

上图显示了不同类型功能的增长趋势。随着问题规模N的不断增大，上述时间复杂度不断增加，算法的执行效率越来越低。

常用算法的时间复杂度为：(1)& lt；(对数)和lt； (n)和lt；(nlog n)& lt； (N2)有限公司； (n3)和lt；…& lt； (2 n)和lt；.)。

值得注意的是，算法的复杂度只是描述了算法的增长趋势，不能说一种算法比另一种算法更高效。将问题规模n的范围相加，在某个问题规范范围之前，一种算法比另一种算法更有效，在某个阈值之后，情况可能会发生逆转。从上图中，我们可以

以明显看到这一点。这也就是为什么我们在实践的过程中得出的结论可能上面算法的排序相反的原因。

如何推导时间复杂度

上面我们了解了时间复杂度的基本概念及表达式，那么实践中我们怎么样才能通过代码获得对应的表达式呢？这就涉及到求解算法复杂度。

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

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

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

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

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

时间复杂度实例

常数阶 O(1)

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

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

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

对数阶 O(log n)

先来看对应的示例代码：

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

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

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

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

线性阶 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) 来表示时间复杂度。

线性对数阶 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)。

平方阶 O(n²)

示例代码：

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)。

如果将外层循环中的 n 改为 m，即：

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

那么，对应的时间复杂度便为：O(m * n)。

同理，立方阶 O(n³)、K 次方阶 O(n^k)，只不过是嵌套了 3 层循环、k 层循环而已。

排序算法对比

上面介绍了各种示例算法的时间复杂度推理过程，对照上面的时间复杂度以及算法效率的大小，来看一下我们常见的针对排序的几种算法的时间复杂度对比。

空间复杂度

最后，我们再了解一下空间复杂度。空间复杂度主要指执行算法所需内存的大小，用于对程序运行过程中所需要的临时存储空间的度量，这里的空间复杂度同样是预估的。

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

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

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

空间复杂度 O(1)

空间复杂度为 O(1) 的情况的示例代码与时间复杂度为 O(1) 的实例代码一致：

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

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

空间复杂度 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)。

总结一下

本篇文章给大家讲了可以通过时间复杂度和空间复杂度来衡量算法的优劣，同时用具体的实例来讲解如何计算不同方法的时间复杂度和空间复杂度。当我们了解了这些基本的概念、函数、计算方法、计算规则及算法性能之后，再进行算法的学习便可以轻松预估出算法的性能等指标。