简单理解时间复杂度

2019-02-20

时间复杂度是一个及基础又重要，但却不那么显性的概念。对于很多程序员来说仿佛只会出现在面试题里，因为不了解它好像也不影响我开发程序。

时间复杂度是算法的一个重要概念，但并不是一句重要就可以逼着别人去学习的，首先我们要提出三问。

第一问，为什么要使用时间复杂度
第二问，什么是时间复杂度
第三问，如何计算时间复杂度
更多的时间复杂度

第一问，为什么要使用时间复杂度

一个算法在证明数学正确性后，我们要关心它的运行时间，这是一个程序性能的重要指标。

算法的时间可以通过实际运行得到，但有两个缺点

复杂的算法通过开发到运行后在又优化，流程会很长，整体操作时间长，很不方便
运行时间受硬件、软件的影响，这对我们评估算法本身存在影响

我们更希望可以在运行前，或者在编写前就预估出可能执行的“时间”。

所以引入了时间复杂度的概念，时间复杂度不是计算算法运行时间，而是估算出算法的复杂度，是个量级的概念。我们可以通过可能出现的时间复杂度，来选择可以接受的算法。

第二问，什么是时间复杂度

时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

简单总结为

n 为算法使用者可以传入的变量，通常时间复杂度受该参数影响。
T(n) 算法的运行次数，次数随着 n 的变化，而变化。
O(f(n)) 算法运行次数变化的规律，也就是时间复杂度，以大写的 O 为符号标记。
f(n) 时间复杂度的值，是个近似值。

举个例子

1	console.log("Hello World");

执行一次 Hello World 语句，我们称为一次运算，这个算法的时间复杂度就是 O(1)，也称为常数阶。

1
2
3

for(var i = 0; i < n; i++){
    console.log(i);
}

在这个算法里，console.log(i); 的执行次数，随着参数 n 的变化而变化，那么这个算法的时间复杂度为 O(n)，也称为线性阶。

for(var i = 0; i < n; i++){
    for(var j = 0; j < n; j++){
        console.log(i + j);
    }
}

在这个算法里，console.log(i + j); 的执行次数为 n * n，那么时间复杂度就是 O(n^2)，也成为平方阶。

在后续的描述中，^ 符号代表后面跟的是上角标，_ 符号代表后面跟着下角标。

通过这几个例子，我们可以得到计算时间复杂度的三个步骤

找出算法的基本运行语句
计算运行次数的量级
使用 O 将其标记起来

第三问，如何计算时间复杂度

计算时间复杂度也就是计算函数 f(n) 的值，是一个量级，在复杂算法中，时间复杂度关心的是最大的量级。

计算方式有如下规则

不受参数 n 影响的运算次数，我们用常量 C 表示，当算法有参数 n 时，C 可以忽略不计，否则用 1 代替。(常数变1，然后去常数，去常参)
不受 for 循环影响的运算次数，使用加减法计算，否则使用乘法计算。
在最后的计算公式中，我们使用最大量级的值，来代表整个算法的时间复杂度。（去低阶）

举几个例子

常量变 1

1
2
3

console.log("Hello World");     // 1
console.log("Hello World");     // 1
console.log("Hello World");     // 1

可以推导出

1 2	f(n) = Θ(1 + 1 + 1) = 1 # Θ 表示常量变1、去常数、去常参、去低阶 T(n) = O(f(n)) = O(1)

去常数

console.log("Hello World");     // 1
console.log("Hello World");     // 1
for(var i = 0; i < n; i++){     // n
    console.log("Hello World"); // 1
}

推导公式

1 2	f(n) = Θ(1 + 1 + n * 1) = Θ(2 + n) = n T(n) = O(f(n)) = O(n)

为什么可以去掉常量？，当 n 趋近无穷大时，所以的常量都可以忽略不计，时间复杂度只关心最大的量级，所以可以去掉常量。

去常参

console.log("Hello World");         // 1
for(var i = 0; i < n; i++){         // n
    console.log("Hello World ");    // 1
}
for(var i = 0; i < n; i++){         // n
    console.log("Hello World ");    // 1
}

推导公式

1 2	f(n) = Θ(1 + n * 1 + n * 1) = Θ(1 + 2n) = n T(n) = O(f(n)) = O(n)

去低阶

for(var i = 0; i < n; i++){         // n
    console.log("Hello World ");    // 1
}
for(var i = 1; i < n; i++){         // n - 1
    for(var j = 1; j < n; j++){     // n - 1
        console.log("Hello World ");// 1
    }
}

推导公式

1 2	f(n) = Θ(n * 1 + (n - 1) * (n - 1) * 1) = Θ(n + n * n) = Θ(n + n^2) = n^2 T(n) = O(f(n)) = O(n)

为什么可以去低阶?，同样的道理，当 n 趋近无穷时，n 在 n^2 的量级面前不止一提，所以我们可以去低阶。

更多的时间复杂度

前面我提到了三种时间复杂度，分别为常数阶 O(1)、线性阶 O(n)、平方阶 O(n^2)

常用的时间复杂度还有：对数阶 O(log_2n)、线性对数阶 O(nlog_2n)、立方阶 O(n^3)、k 次方阶 O(n^k)、指数阶 O(2^n)/O(n!)

对数阶例子

var i = 1
while(1 <= n) {
    i = i * 2
}

推导公式需要使用到对数，假设 while 运行的次数为 k

n = 2^(k-1)
k = log_2n + 1
f(n) = Θ(1 + log_2n + 1) = log_2n
T(n) = O(f(n)) = O(log_2n)

O(n!) 例子

void nFacRuntimeFunc(int n) {
  for(int i=0; i<n; i++) {
    nFacRuntimeFunc(n-1);
  }
}

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log_2n)＜Ο(n)＜Ο(nlog_2n)＜Ο(n^2)＜Ο(n^3)＜…＜Ο(2^n)＜Ο(n!)

常数阶算法不包含任务循环语句和回调函数，我们不用担心此类算法的运算时间
对数阶、线性阶和次方阶，称为多项时间。通常包含循环语句，此类算法归为 P（Polynomial,多项式）类问题
指数阶，称为指数时间。通常包含回调函数，此类算法归为 NP（Non-Deterministic Polynomial, 非确定多项式）问题

一般我们认为常数阶、对数阶、线性阶是可以接收的时间复杂度，因为次方阶和指数阶 n 的变量稍微变大，运行时间就成指数增加，让程序无法动弹。

通过这篇文章应该可以简单的了解时间复杂度，并可以计算常见的算法时间复杂度，但是仍需要不断的练习才可以熟练掌握。

参考资料