算法复杂度分析(一)(算法复杂度分析的两种基本方法)
在我们从事互联网软件技术的时候，我们或多或少会接触到很多的算法，那么到底什么是算法呢？我们看一个很简单的例子：
我们现在要求编写一段程序计算整数 0 到 n 之间所有整数之和。这个问题很简单，相信你马上就可以写出如下的代码：
private static long sum(int n) { long res = 0; for (int i = 0; i <= n; i++) { res += i; } return res; } 复制代码虽然简单，但是它确实是一个算法
如果我们非得给算法下一个定义的话，那算法就是：使用一段程序解决实际问题的方法
注意：实现算法的程序可以是任意计算机语言，比如 Java、C、C++、Python 等，所以说算法是高于语言存在的
怎么评估算法的性能？
很多时候，面对一个算法，我们需要评测这个算法性能，也就是算法的执行时间，如果执行时间越短，那么说明这个算法的性能越好
我们可以通过下面的方式来计算上面【求和】算法的执行时间：
public static void main(String[] args) { long begin = System.currentTimeMillis(); long result = sum(1000000); // 统计计算 0 到 1000000 需要的时间 System.out.println((System.currentTimeMillis() - begin)); System.out.println(result); } 复制代码上面的方式虽然可以得到求和算法的执行时间，但是这种方式有两个非常大的缺点：
算法执行时间非常依赖算法执行环境。在不同处理器的电脑上执行上面的程序，执行时间肯定不一样的
算法执行时间受数据规模的影响。以上我们使用 1000000 作为测试数据，如果我们使用 100、1000、10000 等作为测试数据呢？执行时间肯定不同
除了这两个缺点外，这种性能时间评估方式还有一个非常大的特点：必须要算法实现完了，才能测试算法的性能，一般我们把这种方式称为事后统计法
如果你面对一个很困难的算法问题，你可能花了一整天实现它，但当你使用事后统计法来评估算法执行时间，发现执行时间太长了，这样你可能又需要重新实现算法，这样会浪费不少时间
但是，如果你在实现算法前，通过某种方法，就可以评估你即将要实现的算法的性能，这样你就可以一下子设计并实现最高效的算法了，不用浪费时间了
鉴于以上的性能评估方法【即事后统计法】的几个缺点，所以，我们现在需要一种算法性能评估方法，这个方法应该有以下的三个特点：
不依赖具体的算法执行环境
不用具体的测试数据
在算法实现之前，我们就可以在脑海中评估即将要实现的算法的性能
那么，这种方法就是我们接下来要学习的复杂度分析的方法，我们可以通过复杂度分析的方法来评估一个算法的性能。
如何估算程序段的执行时间？
时间复杂度分析是用来评估一个算法的性能，而本质上来说，评估一个算法的性能就是评估这个算法对应程序段执行的时间
而且，时间复杂度分析是要求在不运行程序段的情况下，来评估程序段的运行时间，这个时候我们就需要一套规则来评估算法的执行时间了
一个算法对应的程序段执行的时间，实际上等于这个程序段中所有的代码运行的时间和，比如我们还是以求和算法的程序段为例：
private static long sum(int n) { long res = 0; // (1) int i = 0; // (2) for (; i <= n; i++) { // (3) res += i; // (4) } return res; // (5) } 复制代码以上程序段执行的时间就是等于第（1）、（2）、（3）、（4）、（5）行代码执行的时间之和。那么，这里存在两个问题：
每行代码执行的时间是多少呢？
每行代码是不是可以循环执行多少次呢？
我们分别来看上面的两个问题。
第一：每行代码执行的时间是多少？
实际情况中，每行代码可能会包含若干个语句，比如上面代码的第（2）行就包括 2 个语句。
站在 CPU 的角度来看，代码中的每个语句都执行着类似的操作：读数据 - 运算 - 写数据，而且每个语句在不同的电脑上执行的时间也是不一样的
所以，为了屏蔽对执行环境的依赖，我们现在假设每个语句执行的时候需要一个单位的时间，至于具体是多长时间，我们不用去关心它
我们把这个单位时间记作为 unit_time，也就是说程序段中的每个语句执行的时间是 unit_time，所以说，每行代码包含了几个语句，那么这一行执行的时间就是几倍的 unit_time
第二：每行代码是不是可以循环执行多次？ 在一个算法程序段中，一行代码可以执行一次，也可以循环执行多次，如下图：
以上：
有 3 个语句执行了 1 次，那么执行时间是 3 * unit_time
有 3 个语句执行了 n 次，那么执行时间是 3n * unit_time
现在，可以计算出上面求和算法的执行时间是：
3 * unit_time + 3n * unit_time，即 (3n + 3) * unit_time
根据上面的分析，可以看出，算法对应程序段的执行时间与所有语句执行的次数成正比\
我们假设使用 T(n) 来表示整个程序段执行时间，那么求和程序段执行时间：
T(n) = (3n + 3) * unit_time\
大 O 复杂度表示法
接下来，我们看一个简单的程序段：
private static long sum2(int n) { long res = 0; // (1) int i = 0; // (2) for (; i <= n; i++) { // (3) int j = 0; // (4) for (; j <= n; j++) { // (5) res = res + (i * j); // (6) } } return res; // (7) } 复制代码我们依然假设每个语句执行时间是 unit_time，那么上面程序段的总执行时间 T(n) 等于多少呢？\
第 (1)、(2)、(7) 行代码都只有一个语句，所以每行都只需要 1 个unit_time，即 3 * unit_time
第 (3) 行有 2 个语句，并且每个语句需要执行 n 次，所以执行时间是 2n * unit_time
第 (4) 行只有 1 个语句，并且执行了 n 次，所以执行时间是 n * unit_time
第 (5)、(6) 行都需要执行 n * n 次，但是第 (5) 行有两个语句，所以总共执行时间是 3n * n * unit_time
以上总的执行时间 T(n) = (3n^2 + 3n + 3) * unit_time
说明：n^2 表示 n 的平方
尽管我们不知道 unit_time 的具体值，但是通过前面两段程序段执行时间的推导，我们可以得到一个非常重要的规律：
所有程序段的执行时间 T(n) 与程序所有行执行次数有关系
我们可以把这个规律总结成一个公式：T(n) = O(f(n))，接下来，我们来解释下这个公式。
T(n) 就是表示算法程序段执行的时间
n 表示的是输入数据规模的大小，可以是任意大小的整数
f(n) 表示程序段所有语句执行的次数总和，因为执行的次数总和是一个输入为 n 的函数，所以我们使用 f(n) 表示
大 O 表示程序段执行时间 T(n) 与 f(n) 函数的关系
所以：
第一个例子中的 f(n) = 3n + 3，那么 T(n) = O(3n + 3)
第二个例子中的 f(n) = 3n^2 + 3n + 3，那么 T(n) = O(3n^2 + 3n + 3)
这就是大 O 时间复杂度表示法，大 O 时间复杂度实际上并不是具体表示代码真正的执行时间，而是表示代码执行时间随着数据规模增长的变化趋势，所以也叫做渐进时间复杂度，我们一般简称时间复杂度
随着数据规模 n 的不断增大，以上 T(n) 中的系数、低阶、常量对执行时间的增长趋势影响非常的小，所以，一般在做时间复杂度分析的时候，会将这三部分省略掉
我们只需要记录最高阶的项就可以了，这样，上面两段程序段的时间复杂度就可以表达为：
第一段程序段：T(n) = O(n)
第二段程序段：T(n) = O(n^2)
除了 O(n) 和 O(n^2) 两种常见的时间复杂度，我们可能还会遇到 O(n^3)，甚至 O(n^4)，我们来看下面一段程序：
for (int i = 1; i <= n; i++) { // (1) for (int j = 1; j <= n; j++) { // (2) for (int k = 1; k <= n; k++) { // (3) System.out.println(i + j + k); // (4) } } } 复制代码我们现在按照之前的方法来对上面的程序段的时间复杂度进行分析
第一行有 3 个语句，其中第一个语句执行 1 次，第二个和第三个语句执行了 n 次，那么这一行的执行时间是：(2n + 1) * unit_time
第二行有 3 个语句，其中第一个语句执行了 n 次，第二个和第三个语句执行了 nn 次，那么这一行的执行时间是：(2nn + n) * unit_time
第三行有 3 个语句，其中第一个语句执行了 nn 次，第二个和第三个语句执行了 nnn 次，那么这一行的执行时间是：(2nnn + nn) * unit_time
第四行有 1 个语句，执行了 nnn 次
以上总的执行时间是：(3n^3 + 3n^2 + 3n + 1) * unit_time，那么执行次数 f(n) = (3n^3 + 3n^2 + 3n + 1)
所以时间复杂度 T(n) = O(3n^3 + 3n^2 + 3n + 1)，去掉系数、常量、低阶，那么 T(n) = O(n^3)
那么除了这两种复杂度，常用的复杂度还包括：O(1)、O(logn)。接下来我们分别来介绍这两种常见的复杂度。
常量级别的复杂度：O(1)
我们先看下面的一段程序：
int x = 5; int y = 10; int result = x + y; System.out.println(result); 复制代码
请问，上面的程序段的时间复杂度是多少？
我们知道上面程序段中有 4 个语句需要执行，按照前面的分析，执行时间是 4 * unit_time，也就是说 f(n) = 4，这个公式表示程序的执行时间和数据规模 n 没有关系
即程序执行的时间不随着数据规模 n 的增长而增长，所以，这种程序的时间复杂度我们称为常量级时间复杂度
对于上面的常量级时间复杂度，我们不用 O(4) 来表示，而是使用 O(1) 来表示
也就是说，只要你的程序段执行的时间和输入数据规模 n 没有关系的话，即使需要执行成千上万行的代码，那么你的程序时间复杂度仍然是 O(1)
一般情况下，只要算法中不存在循环语句、递归语句，那么算法的时间复杂度就是 O(1)。但是也有特例，我们看下面的代码：
int sum = 0; for (int i = 0; i <= 10000; i++) { sum += i; } 复制代码上面的程序虽然有循环语句，但是这段程序的执行时间和数据规模 n 没有关系，所以，这段程序的时间复杂度仍然是 O(1)
对数级别的复杂度：O(logn)
看下面的一段程序：
int i = 1; // (1) for (; i <= n; i += i) { // (2) System.out.println(i); // (3) } 复制代码请问，上面代码的时间复杂度是多少？
按照前面的复杂度分析思路，我们先计算每行代码的执行时间：
第一行代码只有一个语句，而且只执行一次，所以执行时间是 1 个 unit_time
第二行代码和第三行代码需要执行的次数是一样的，那到底是执行了多少次呢？看如下的分析：
我们得到，第二行代码和第三行代码需要执行的次数是 1 + log2n，第二行代码有 2 个语句，所以第二行和第三行执行时间是：(3log2n + 3) * unit_time
log2n 表示以 2 为底的对数
上面代码的总的执行时间是：(3log2n + 4) * unit_time，所以 f(n) = 3log2n + 4。那么时间复杂度 T(n) = O(3log2n + 4)，去掉系数和常量，那么 T(n) = O(log2n)
我们现在再来看一段代码
int i = 1; // (1) for (; i <= n; i = i * 3) { // (2) System.out.println(i); // (3) } 复制代码那么这段代码的时间复杂度是多少呢？我们也可以按照上面的思路来分析。
从上面可以得出，上面的代码的时间复杂度是 O(log3n)。
在学习对数的时候，我们知道，两个对数是可以相互转化的，比如：
所以：
在计算时间复杂度的时候，我们一般忽略系数、常量以及低阶，所以上面的等式可以改成：
由此，我们就可以得出结论：
也就是说，以任意数为底的对数阶复杂度都是相等的，因此，在对数阶时间复杂度的表示方法中，我们忽略对数的底，统一表示为 O(logn)
小结
前面我们介绍了大 O 时间复杂度表示法，以及我们也知道了几种常见的时间复杂度。那么现在如果给你一段代码，你会怎么样去分析代码的时间复杂度呢？
我们对前面分析时间复杂度方法流程做一个总结：
首先，计算每行每个语句执行的次数
然后，计算所有语句执行的总次数
最后，对总次数的表达式进行去系数、低阶、常数
可以参考下面的流程图：
从上图，我们可以得出一个结论：在分析一段代码时间复杂度的时候，我们只需要关注关注这段代码中执行次数最多的那段代码
比如上面的代码中执行次数最多的就是第三层循环中的打印语句，一共执行了 n^3 次，所以整个代码段的时间复杂度是 O(n^3)
作者：老汤说算法
链接：https://juejin.cn/post/7032489291376918565