LeetCode0：学习算法必备知识：时间复杂度与空间复杂度的计算
算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。算法是大厂、外企面试的必备项，也是每个高级程序员的必备技能。针对同一问题，可以有很多种算法来解决，但不同的算法在效率和占用存储空间上的区别可能会很大。
那么，通过什么指标来衡量算法的优劣呢？其中，上面提到的效率可以用算法的时间复杂度来描述，而所占用的存储空间可以用算法的空间复杂度来描述。
- 时间复杂度：用于评估执行程序所消耗的时间，可以估算出程序对处理器的使用程度。
- 空间复杂度：用于评估执行程序所占用的内存空间，可以估算出程序对计算机内存的使用程度。
在实践中或面试中，我们不仅要能够写出具体的算法来，还要了解算法的时间复杂度和空间复杂度，这样才能够评估出算法的优劣。当时间复杂度和空间复杂度无法同时满足时，还需要从中选取一个平衡点。
一个算法通常存在最好、平均、最坏三种情况，我们一般关注的是最坏情况。最坏情况是算法运行时间的上界，对于某些算法来说，最坏情况出现的比较频繁，也意味着平均情况和最坏情况一样差。
通常，时间复杂度要比空间复杂度更容易出问题，更多研究的是时间复杂度，面试中如果没有特殊说明，讲的也是时间复杂度。
时间复杂度
要获得算法的时间复杂度，最直观的想法是把算法程序运行一遍，自然可以获得。但实践中往往受限于测试环境、数据规模等因素，直接测试算法要么难以实现，要么误差较大，而且理论上也没必要对每个算法都进行一遍测试，只需要找到一种评估指标，获得算法执行所消耗时间的基本趋势即可。
时间频度
通常，一个算法所花费的时间与代码语句执行的次数成正比，算法执行语句越多，消耗的时间也就越多。我们把一个算法中的语句执行次数称为时间频度，记作T(n)。
渐进时间复杂度
在时间频度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)。简单来说，就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。也就是说当n趋于正无穷时T(n)的上界是C * f(n)。其虽然对f(n)没有规定，但是一般都是取尽可能简单的函数。
常见的时间复杂度有：O(1)常数型；O(log n)对数型，O(n)线性型，O(nlog n)线性对数型，O(n^2)平方型，O(n^3)立方型，O(n^k)k次方型，O(2^n)指数型。
上图为不同类型的函数的增长趋势图，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜Ο(n^2)＜Ο(n^3)＜…＜Ο(2^n)＜Ο(n!)。
值得留意的是，算法复杂度只是描述算法的增长趋势，并不能说一个算法一定比另外一个算法高效。这要添加上问题规模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。如果用公式表示就是1222…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)。
总结一下
本篇文章给大家讲了可以通过时间复杂度和空间复杂度来衡量算法的优劣，同时用具体的实例来讲解如何计算不同方法的时间复杂度和空间复杂度。当我们了解了这些基本的概念、函数、计算方法、计算规则及算法性能之后，再进行算法的学习便可以轻松预估出算法的性能等指标。
参考文献：
https://blog.csdn.net/zolalad/article/details/11848739
https://zhuanlan.zhihu.com/p/50479555
关注公众号：程序新视界，一个让你软实力、硬技术同步提升的平台
除非注明，否则均为程序新视界原创文章，转载必须以链接形式标明本文链接
