怎么计算我们自己程序的时间复杂度

发布于

知道自己写的程序的时间复杂度，有利于我们写出能够高效运行的程序。

程序是由一个个函数组成的，有些简单的由几个基础运算组成的函数大家一眼就能看出来它的时间复杂度，但是大部分函数没那么简单，只要函数里面涉及到了循环、外部函数调用甚至递归的时候它的时间复杂度就没那么容易分析啦。

这篇文章的内容，可以帮你快速推导出程序代码的时间复杂度。

要分析程序的时间复杂度，首先还是要确定时间复杂度的度量标准— —英文文档里通常会用 metric 这个单词来表示，这个标准规定了在函数中平铺展开的代码、循环中的代码、有函数调用的代码、以及递归调用的代码的时间复杂度的测量方式。

Big O Notations

如何计算程序的时间复杂度呢？最常用的度量方式叫做 Big O Notations 翻译过来叫大O标记法。

使用大O标记法前要先了解它的几个要点：

  • 相同配置的计算机进行一次基本运算的时间是一定的，因此我们将程序基本运算的执行次数作为时间复杂度的衡量标准。
  • 时间复杂度是对运行次数的错略估计，在计算时可以只考虑对运行时间贡献大的语句而忽略运行次数少的语句。比如 O(3 * n2 + 10n + 10) 会被统计成 O(n2)。
  • 比如有些涉及到排序的程序，执行时间往往依赖于程序的输入，可以分为最好、最坏、平均情况的时间复杂度，这种时候使用大 O 标记法时我们只用关注最坏的情况，因为最坏情况对衡量程序效率的好坏具有实际意义。

在大O标记法中，常见的时间复杂度有一下几类。

  1. 常数阶: 常数阶的复杂度通常用O(1)表示，不是说程序只有一行基础代码运行，它的意思是不管程序的输入是什么程序都会运行一个固定数量的运算，这个数可以是任何常数5、100、200都行，重点是他不会随输入的增长才被统计称 O(1)
  2. 多项式阶： 很多算法的时间复杂度是 O(n)、O(n2)、O(n3)这样的多项式。
  3. 指数阶： 指数阶的时间复杂度用O(2n) 、 O(nn) 等表示，这种程序运行效率极差，是程序员写代码一定要避开的大坑。
  4. 对数阶： 对数阶的程序运行效率较高，通常用O(logn)、 O(n log n) 等表示。

它们的关系如下：

从上面的图我们可以看到，O(1)是最高效最稳定的，完全不受输入数据尺寸增长的影响，指数阶随着输入的增加而爆增，而对数阶则增长缓慢。

按照时间复杂度从低到高排序：

O(1) < O(logn) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

在写程序时，我们要注意时间复杂度增量的问题，尽量避免爆炸级增长。

了解完时间复杂度的大O标记法后，接下来我们看下怎么把我们平时接触的代码转化为其对应的时间复杂度。

顺序语句的复杂度

这是最简单的代码结构，比如说我们有一个下面的计算3个数字的平方和的函数。

代码语言：javascript
复制
function squareSum(a, b, c) {
  const sa = a * a;
  const sb = b * b;
  const sc = c * c;
  const sum = sa + sb + sc;
  return sum;
}

函数中的每个语句都是一个基本运算。每行的时间复杂度为 O(1)。我们把所有语句的时间加起来，它仍然是 O(1)， 记住昂，不是O(3)。

O(1)表示程序时常数级的时间复杂度，不管程序的输入是什么程序都会运行数量固定的操作。

注意如果顺序排列的代码中有对函数的调用，复杂度就不是O(1)了，你想知道是多少？继续接着看后面的文章

条件语句的复杂度

很少有会有程序代码没有任何条件语句。因为大 O 标记法关注程序运行的的最坏情况，所以对一个类似这样的条件语句：

代码语言：javascript
复制
if (isValid) {
  statement1;
  statement2;
} else {
  statement3;
}

它的时间复杂度可以按下面这个公式推导出来：

代码语言：javascript
复制
T(n) = Math.max([t(statement1) + t(statement2)], [time(statement3)])

比如说下面这个代码

代码语言：javascript
复制
if (isValid) {
  array.sort();
  return true;
} else {
  return false;
}

if代码块中的时间复杂度为O( n log n) — 常用编程语言内置排序算法的时间复杂度，else代码块的时间复杂度为O(1)，那么整个代码的时间复杂度为：

代码语言：javascript
复制
O([n log n] + [n]) => O(n log n)

循环语句的复杂度

线性循环

代码语言：javascript
复制
for (let i = 0; i < array.length; i++) {
  statement1;
  statement2;
}

对于这个例子，循环执行 array.length次，所有与输入数据增长而成比例增长的循环都具有线性—常数阶的时间复杂度 O(n)。

对数循环

观察下面的程序

代码语言：javascript
复制
function fn(n) {
  i = 1;
  while( i < n) {
     i = i*2;
  }
 }

对于这个程序，我们无法确定while 以及 i = i*2 语句运行了多少次，这时可以假设运行了x次，每次运行后i的值为2、22、23… 当while 语句的条件不满足即i = n时结束，也就是2x = n ， x = log2n ，它的时间复杂度近似于O(logn )。

固定次数循环

代码语言：javascript
复制
for (let i = 0; i < 4; i++) {
  statement1;
  statement2;
}

针对固定条件的循环，像上面这个程序一样，无聊时固定循环4次还是 100 次时间复杂度都是 O(1)

嵌套循环

代码语言：javascript
复制
for (let i = 0; i < n; i++) {
  statement1;

for (let j = 0; j < m; j++) {

statement2;

statement3;

}

}

假设循环中的语句都是基础操作，没有对函数的调用，那么这个代码有两层嵌套循环，时间复杂度为O(n2)。

循环中有函数调用的时间复杂度

假如我们有这样一个程序：

代码语言：javascript
复制
for (let i = 0; i < n; i++) {

fn1();

for (let j = 0; j < n; j++) {

fn2();

for (let k = 0; k < n; k++) {

fn3();

}

}

}

根据 fn1、fn2 和 fn3 函数自身的时间复杂度，整个程序将拥有不同的运行时间。

如果这三个函数它们都是常数阶 O(1)，那么最终的运行时间将为 O(n3)。但是如果只有 fn1 和 fn2 是常数介， fn3 的时间复杂度为 O(n2)，则该程序的运行时间将为 O(n5)。

一般来说，循环中有函数调用，时间复杂度可以用下面这个公式计算：

代码语言：javascript
复制
T(n) = n * [ t(fn1()) + n * [ t(fn2()) + n * [ t(fn3()) ] ] ]

函数递归调用的时间复杂度

代码语言：javascript
复制
function fn(n) {

if (n == 1 || n == 2) {

return 1;

}

return fn(n - 1) + fn(n - 2);

}

以上是学算法都学过的斐波那切数列的递归调用实现版本，它的时间复杂度为O(2n) ，所以在平时写代码时在你不确定程序能执行多少次的时候，最好不要轻易使用递归调用。

总结

这篇内容我们梳理了一下不同的时间复杂对大概对应什么样的代码，让我们能更正确地估算自己写的程序的时间复杂度。在写程序时，我们要注意时间复杂度增量的问题，尽量避免爆炸级增长。

结尾推荐一下我用大半年的时间沉淀，汇集了我多年职场经验的画图课，解决程序员普遍只愿意埋头写代码，不会做需求分析、不会做技术评审、不会画架构图、述职汇报做不好，等等这些需要画图和表达能力的事情的时候就犯难的问题，帮助大家摆脱代码的单一维度，从多维度提升自己，建立自信，让你在工作中更游刃有余。

#函数#基础#效率#程序#递归