在学习具体的数据结构之前，都要掌握什么是时间复杂度、什么是空间复杂度。空间复杂度和时间复杂度是衡量一个算法的运行效率的标准
时间复杂度
- 判断一个算法所编程序运行时间的多少，并不是将程序编写出来，通过在计算机上运行所消耗的时间来度量。原因很简单，一方面，解决一个问题的算法可能有很多种，一一实现的工作量无疑是巨大的，得不偿失；另一方面，不同计算机的软、硬件环境不同，即便使用同一台计算机，不同时间段其系统环境也不相同，程序的运行时间很可能会受影响，严重时甚至会导致误判。
- 实际场景中，我们更喜欢用一个估值来表示算法所编程序的运行时间。所谓估值，即估计的、并不准确的值。注意，虽然估值无法准确的表示算法所编程序的运行时间，但它的得来并非凭空揣测，需要经过缜密的计算后才能得出。
- 也就是说，表示一个算法所编程序运行时间的多少，用的并不是准确值（事实上也无法得出），而是根据合理方法得到的预估值。
- 那么，如何预估一个算法所编程序的运行时间呢？很简单，先分别计算程序中每条语句的执行次数，然后用总的执行次数间接表示程序的运行时间。
实例如下
public class TimeComplexity {// 时间复杂度 程序执行中经历的次数public static void main(String[] args) {case1();}private static void case1() {int n = 1000;int a = 0;// 为什么这里是n+1次，因为当i增长到n的时候，还需要进行一次判断，才能结束循环for (int i = 0; i < n; i++) { // 从 0 到 n，执行 n+1 次a++; // 从 0 到 n-1，执行 n 次}System.out.println(a);}}
这段程序只有2行代码，其中
- for循环i的值从0增长到n（注意，循环退出的时候i的值为n）因此for循环语句执行了n+1次
- 而循环内部仅有一条语句，a++从i的值为0的时候就开始执行，i的值没增加1，该语句就执行一次，一直到i的值为n-1，因此，a++语句执行了n次。
- 因此：整段代码中所有语句共执行了 (n+1)+n 次，即 2n+1 次。数据结构中，每条语句的执行次数，又被称为该语句的频度。整段代码的总执行次数，即整段代码的频度。
- 再举一个例子
```java
public class TimeComplexity {
// 时间复杂度 程序执行中经历的次数
public static void main(String[] args) {
} private static void case2() {case2();
} }int n = 1000; int m = 1000; int a = 0; for (int i = 0; i < n; i++) { // 从 0 到 n，执行 n+1 次 // n次 for (int j = 0; j < m; j++) { // n*(m+1) // m次 a++; // n*(m) } } System.out.println(a);
- 时间复杂度为：(n+1)+n*(m+1)+n*m = 2*n*m+2*n+1
- 值得一提的是，不同程序的运行时间，更多场景中比较的是在最坏条件下程序的运行时间。以上面这段程序为例，最坏条件即指的是当 n、m 都为无限大时此段程序的运行时间。
- 要知道，当 n、m 都无限大时，我们完全就可以认为 n==m。在此基础上，2*n*m+2*n+1 又可以简化为 2*n^2+2*n+1，这就是此段程序在最坏情况下的运行时间，也就是此段程序的频度。
- 如果比较以上 2 段程序的运行时间，即比较 2n+1 和 2*n^2+2*n+1 的大小，显然当 n 无限大时，前者要远远小于后者
- 显然，第 1 段程序的运行时间更短，运行更快。
- 思考一个问题，类似 2n+1、2*n^2+2*n+1 这样的频度，还可以再简化吗？答案是肯定的
- 以 2n+1 为例，当 n 无限大时，是否在 2n 的基础上再做 +1 操作，并无关紧要，因为 2n 和 2n+1 当 n 无限大时，它们的值是无限接近的。甚至于我们还可以认为，当 n 无限大时，是否给 n 乘 2，也是无关紧要的，因为 n 是无限大，2*n 也是无限大。
- 再以无限大的思想来简化 2*n^2+2*n+1。当 n 无限大的：
- 首先，常数 1 是可以忽略不计的；
- 其次，对于指数级的 2*n^2 来说，是否在其基础上加 2*n，并无关紧要；
- 甚至于，对于是否给 n^2 乘 2，也可以忽略。
- 因此，最终频度 2*n^2+2*n+1 可以简化为 n^2
- 对于“使用无限大的思想”简化频度表达式，在数据结构中，频度表达式可以这样简化
- 去掉频度表达式中，所有加法常数的式子。例如：例如 2n^2+2n+1 简化为 2n^2+2n
- 如果表达式有多项含有无限大变量的式子，只保留一个拥有指数最高的变量的式子。例如 2n^2+2n 简化为 2n^2
- 如果最高项存在系数，且不为 1，直接去掉系数。例如 2n^2 系数为 2，直接简化为 n^2
- 事实上，对于一个算法（或者一段程序）来说，其最简频度往往就是最深层次的循环结构中某一条语句的执行次数。例如 2n+1 最简为 n，实际上就是 a++ 语句的执行次数；同样 2n^2+2n+1 简化为 n^2，实际上就是最内层循环中 a++ 语句的执行次数。
- 得到最简频度的基础上，为了避免人们随意使用 a、b、c 等字符来表示运行时间，需要建立统一的规范。数据结构推出了大 O 记法（注意，是大写的字母 O，不是数字 0）来表示算法（程序）的运行时间。发展至今，此方法已为大多数人所采纳。
- 大 O 记法的表示方法也很简单，格式如下：**O(频度) **这里的频度为最简之后所得的频度。
- 用大 O 记法表示上面 2 段程序的运行时间，则上面第一段程序的时间复杂度为 O(n)，第二段程序的时间复杂度为 O(n^2)
- **O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)(立方阶) < O(2^n) (指数阶)**
- 注意，这里仅介绍了以最坏情况下的频度作为时间复杂度，而在某些实际场景中，还可以用最好情况下的频度和最坏情况下的频度的平均值来作为算法的时间复杂度。
<a name="eVxxK"></a>
# 空间复杂度
- 和时间复杂度类似，一个算法的空间复杂度，也常用大 O 记法表示。
- 要知道每一个算法所编写的程序，运行过程中都需要占用大小不等的存储空间，例如：
- 程序代码本身所占用的存储空间；
- 程序中如果需要输入输出数据，也会占用一定的存储空间；
- 程序在运行过程中，可能还需要临时申请更多的存储空间。
- 首先，程序自身所占用的存储空间取决于其包含的代码量，如果要压缩这部分存储空间，就要求我们在实现功能的同时，尽可能编写足够短的代码
- 程序运行过程中输入输出的数据，往往由要解决的问题而定，即便所用算法不同，程序输入输出所占用的存储空间也是相近的。
- 事实上，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的临时存储空间。不同的算法所编写出的程序，其运行时申请的临时存储空间通常会有较大不同。
```java
public class SpaceComplexity {
public static void main(String[] args) {
int n = 10;
int[] ints = new int[10];
}
/**
* 运行时候才会创建多少的空间
*/
private int[] ints(int n) {
return new int[n];
}
}
- 所以，如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 O(1)；反之，如果有关，则需要进一步判断它们之间的关系：
- 如果随着输入值 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示;
- 如果随着输入值 n 的增大，程序申请的临时空间成 n2 关系增长，则程序的空间复杂度用 O(n^2) 表示；
- 如果随着输入值 n 的增大，程序申请的临时空间成 n3 关系增长，则程序的空间复杂度用 O(n^3) 表示；
- 在多数场景中，一个好的算法往往更注重的是时间复杂度的比较，而空间复杂度只要在一个合理的范围内就可以。为什么：因为空间可以买，时间则不可以。
参考文章
- 时间复杂度和空间复杂度：http://data.biancheng.net/view/272.html
若有收获，就点个赞吧
0 人点赞
