烦不烦，别再问我时间复杂度了：这次不色，女孩子进来吧

一、why：为什么要使用时间复杂度

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

       师傅：程序的运行时间如何得到呢？

       悟纤：这个还不简单，在代码开始之前得到开始时间，在代码结束的时候得到结束时间，通过（结束时间-开始时间），这不就得到了运行时间了嘛。

       师傅：那这样子是不是势必就要运行程序才能得到这个运行时间呢？如果都是能够快速运行完的代码，这样子也不错，能够精确的得到代码的执行时间，如果是一个复杂的算法需要运行的比较久的话，那么这个时候就会比较痛苦了，修改一下算法就需要再运行一下。

 

       所以通过实际运行得到算法的时间的话，有这么几个小缺点：

（1）复杂的算法通过开发到运行后在又优化，流程会很长，整体操作时间长。

（2）运行时间受硬件、软件的影响，这对我们评估算法本身存在影响。

       我们是否可以做到在运行前，或者在编写前就预估出可能执行的“时间”。

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

BTW：通过时间复杂度来预估算法的复杂程度，并不能够计算算法的运行时间。

 

二、what：什么是时间复杂度

2.1 概念

在引入时间复杂度的概念的时候，我们需要先来了解另外一个概念时间频度：

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

BTW：

（1）在概念中要求T(n)/f(n)的极限值为不等于零的常数，这个常数不妨理解为O（大O，不是零），那么等式就是T(n)/f(n) = O，变型一下就是为T(n) = O( f(n) ) ，这个等式我们一般这么读，T(n)的时间复杂度为O(f(n))。

（2）n 为算法使用者可以传入的变量，通常时间复杂度受该参数影响。

（3）T(n) 算法的运行次数，次数随着 n 的变化，而变化。

（4）O(f(n)) 算法运行次数变化的规律，也就是时间复杂度，以大写的 O 为符号标记。

（5）f(n) 时间复杂度的值，是个近似值。

最坏时间复杂度：

最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

 

2.2 举个栗子

 我们先通过一些小栗子来理解这个时间频度和时间复杂度吧。

「以下代码是JS代码」

栗子1：

console.log("hello,悟纤");

执行一次console.log我们进行一次运算，那么T(n) = 1，这个算法的时间复杂度就是O(1)，也称为常数阶。

栗子2：

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

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

栗子3：

  1. for(var i =0; i < n; i++){
  2.     for(var j =0; j < n; j++){
  3.         console.log(i + j);
  4.     }
  5. }

 

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

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

（1）找出算法的基本运行语句

（2）计算运行次数的量级

（3）使用 O 将其标记起来

       通过上面的例子中，会有一种误区就是O( f(n) ) 中的f(n) 就等于T(n)，这是错误的。

那么时间复杂度是如何计算的呐？

 

三、how：如何计算时间复杂度

3.1 计算方式

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

计算方式有如下规则：

（1）不受参数 n 影响的运算次数，我们用常量 C 表示，当算法有参数n 时，C 可以忽略不计，否则用 1 代替。(常数变1，然后去常数，去常参)。

（2）不受 for 循环影响的运算次数，使用加减法计算，否则使用乘法计算。

（3）在最后的计算公式中，我们使用最大量级的值，来代表整个算法的时间复杂度。（去低阶）

   有点抽象吧，还是举例说明。

3.2 举个栗子

栗子：常量变 1

  1. console.log("hello,悟纤");
  2.  
  3. console.log("hello,师傅");
  4.  
  5. console.log("hello,八戒");

公式推导如下：

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

所以上面的算法时间复杂度为：O(1)

 



栗子：去常数

 

  1. console.log("Hello World");     // 1
  2.  
  3. console.log("Hello World");     // 1
  4.  
  5. for(var i =0; i < n; i++){     // n
  6.  
  7.     console.log("HelloWorld"); // 1
  8.  
  9. }

 

公式推导如下↓↓↓：

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

所以上面的算法时间复杂度为：O(n)

BTW：为什么可以去掉常量？当 n 趋近无穷大时，常亮对最终的结果来说已经是无足轻重了，时间复杂度只关心最大的量级，所以常量可以忽略不计。

 

栗子：去常参

 

  1. console.log("Hello World");         // 1
  2.  
  3. for(var i =0; i < n; i++){         // n
  4.  
  5.     console.log("Hello World ");    // 1
  6.  
  7. }
  8.  
  9. for(var i =0; i < n; i++){         // n
  10.  
  11.     console.log("Hello World ");    // 1
  12.  
  13. }

公式推导如下↓↓↓：

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

所以上面算法的时间复杂度为：O(n)。

BTW：当n趋近无限大的时候，n前面的系数，对于结果就影响比较小，可以n前面的系数就可以忽略不计。

 

栗子：去低阶

  1. for(var i =0; i < n; i++){         // n
  2.  
  3.     console.log("Hello World ");    // 1
  4.  
  5. }
  6.  
  7. for(var i =1; i < n; i++){         // n - 1
  8.  
  9.     for(var j =1; j < n; j++){     // n - 1
  10.  
  11.         console.log("Hello World ");// 1
  12.  
  13.     }
  14.  
  15. }

公式推导如下↓↓↓：

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

那么上面算法的时间复杂度就是：O(n²)

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

 

四、常见的时间复杂度

 

常用时间复杂度所耗费时间从小到大依次为：

 

在上图中，我们可以看到当 n 很小时，函数之间不易区分，很难说谁处于主导地位，但是当 n 增大时，我们就能看到很明显的区别，谁是老大一目了然：

O(1) < O(logn) < O(n)< O(nlogn) < O(n^2) < O(n^3) < O(2^n)

 

五、其它要点

5.1 时间频度不同，时间复杂度可能相同

举例说明↓↓↓：

T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。

5.2 复杂度默认指的就是时间复杂度

通常没有特别指明时，复杂度指的是时间复杂度，我们写代码时，要学会以空间来换取时间。

 

六、题外话

我们来看一下对数阶的推导过程，代码如下：

  1. var i =1;
  2.  
  3. while(i <= n){
  4.  
  5.    i = i *2;
  6.  
  7. }

代码解读：

n是一个不确定的数，有一个while循环，结束的条件是i<=n的值，在循环体内 i的值是2倍的增加。

时间复杂度推导：

对于：var i=1，代码执行一次，那么关键是循环体的while循环需要执行多少次，决定了算法的时间复杂度。

这个while循环到底需要运行多少次呢？这个是未知数，我们使用变量k来表示，那么通过循环的结束条件i<=n的时候，循环结束，可以得到一个公式，我们看一下具体的推导过程：

  1. 1<=n  // 执行1次判断，0次循环体
  2.  
  3. 1*2<=n  // 执行2次判断，1次循环体
  4.  
  5. 1*2*2<=n  // 执行3次判断，2次循环体
  6.  
  7. 1*2*2*2<=n  // 执行4次判断，3次循环体
  8.  
  9. ….
  10.  
  11. 当假设循环体需要执行k次的时候，那么循环体也就是k-1次了，
  12.  
  13. 那么就可以推导得到如下等式：
  14.  
  15. 1*2^（k-1）=2^（k-1）<=n
  16.  
  17. 通过这个等式就可以推导出来k的值为：
  18.  
  19. k<=log(2)(n)+1，最大值就是k=log(2)(n)+1
  20.  
  21. 这时候就可以计算得到时间频度T(n)= 1+log(2)(n)+1。
  22.  
  23. 那么f(n)=θ( 1+log(2)(n)+1 ) 
     = log(2)(n)时间复杂度：
T(n) = O(f(n))    = O(log(2)(n))

       通过以上分析，上面的算法的时间复杂度为：O( log(2)(n) ) 。【log(2)(n)表示以2为底n的对数】

BTW：对数公式是数学中的一种常见公式，如果a^x=N(a>0,且a≠1)，则x叫做以a为底N的对数 , 记做x=log(a)(N)。

 

七、悟纤小结

       师傅：为师今天讲了很多，悟纤，来，你给大家做个总结吧。

（1）为什么需要时间复杂度：通过时间复杂度可以来预估算法的复杂程度。

（2）时间频度：算法运行次数就是时间频度，使用T(n) 表示，举例说明：n的双层for循环，那么T(n) = n²。

（3）时间复杂度：算法运行次数变化的规律就是时间复杂度，使用O(f(n)) 来表示，举例说明：双层for的f(n) = Θ( n² ) = n² ，所以T(n) = n²的时间复杂度就是O(n²)。

（4）时间复杂度计算规则：常量取1「T(n) = C : O(1)」；n碰到常数，去常数「T(n)=n+c：O(n)」；n前系数，直接去「T(n)=cn : O(n)」; 高阶碰低阶，底阶靠边站 「 T(n) =n²+n：O(n²) 」。（复杂一些的时间复杂度是需要通过计算才能进行推导出来的）

  1. 我就是我，是颜色不一样的烟火。
  2. 我就是我，是与众不同的小苹果。
    





    购买完整视频，请前往：http://www.mark-to-win.com/TeacherV2.html?id=287