算法复杂度分析(一)(算法复杂度分析的两种基本方法)
在我们从事互联网软件技术的时候,我们或多或少会接触到很多的算法,那么到底什么是算法呢?我们看一个很简单的例子:
我们现在要求编写一段程序计算整数 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