算法复杂度

算法复杂度

算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源的统计分析，资源包括时间资源和空间资源

两种统计方式

事后统计

该方法有两个缺陷：
一是要想对设计的算法的运行性能进行评测，必须先依据算法编制相应的程序并实际运行
二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优势

事前分析

对算法的分析取决于以下因素

• 算法选用何种策略
• 问题的规模，例如求100以内还是10000以内的素数
• 编程语言，同一个算法，语言级别越高，通常执行效率就越低
• 编译程序产生的机器代码的质量
• 机器执行指令的速度

复杂度分类

分为时间复杂度和空间复杂度，随着计算机内存的不断增大，目前比较关注的是时间复杂度，通常时间复杂度与空间复杂度是互斥的，以空间换时间或是以时间换空间，但也有空间和时间都很低的复杂度算法，这通常是一种创新的算法

时间复杂度

从算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行次数作为算法的时间复杂度，用符号大 O 表示,即 T(n) = O(f(n))
例如：把变量的赋值操作当做基本原操作，执行 1 次，时间复杂度为 O(1), 执行 n 次，时间复杂度为 O(n)

// 时间复杂度为O(1)
a = 1

// 时间复杂度为O(n)
for (i = 0; i < n; i++)
    a++
    
// 时间复杂度为O(n²)
for (i = 0; i < n; i++)
    for (k = 0; k < n; k++)
        a++

在一个多项式复杂度的算法中，时间复杂度以最高项的阶数为算法的时间复杂度

• 算法中语句执行次数为一个常量阶时，则时间复杂度为O(1), 多项式表达式为 y = a + b，a 和 b 均为常量
• 算法中语句执行次数为一个线性阶时，则时间复杂度为O(n), 多项式表达式为 y = a * n + b，a 和 b 均为常量
• 算法中语句执行次数为一个平方阶时，则时间复杂度为O(n2), 多项式表达式为 y = a * n² + a * n + b，a 和 b 均为常量

时间复杂度的图标

20130920210031796.png
image.png

n	logn	√n	nlogn	n²	2ⁿ	n!
5	2	2	10	25	32	120
10	3	3	30	100	1024	3628800
50	5	7	250	2500	约10^15	约3.0*10^64
100	6	10	600	10000	约10^30	约9.3*10^157
1000	9	31	9000	1000000	约10^300	约4.0*10^2567

常见的时间复杂度量级有：

常数阶O(1)

i = 100
++i

对数阶O(logn)

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

线性阶O(n)

a = 1
for(i = 0; i < n; i++)
   a++

线性对数阶O(nlogn)

log通常指已 2 为底数的对数，lg 指已 10 为底数的对数，ln 指已 e 为底数的对数

for(k=1; k<n; k++) {
    i = 1
    while(i < n) {
        i = i * 2
    }
}

平方阶O(n²)

a = 1
for (i = 0; i < n; i++)
    for (k = 0; k < n; k++)
        a++

// n(n-1)/2
for (i = 0; i < n; i++)
  for (k = i; k < n; k++)
    a++

立方阶O(n³)

a = 1
for (i = 0; i < n; i++)
    for (k = 0; k < n; k++)
        for (j = 0; j < n; j++)
            a++

K次方阶O(n^k)

k 重循环,每重循环执行 n 次

指数阶(2^n)

// 斐波那契额数列
function Fibonacci (n) {
  if ( n <= 1 ) {return 1};
  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

阶乘阶(n!)

n!指的是 n * (n - 1) * (n - 2) ... * 2 * 1

全排列

延伸知识：NP完全问题(NP-C问题)
多项式时间复杂度的这类问题称为P（Polynomial,多项式）类问题，而把非多项式时间复杂度的问题(比如指数时间复杂度等)为NP（Non-Deterministic Polynomial, 非确定多项式）问题，通常认为两者的难度不同，NP完全问题是世界七大数学难题之一(奖金$100万)，NP=P？是否成立现在还未知

编写代码中常用内置函数的算法的时间复杂度

• 排序算法 O(nlogn)，这个是平均时间复杂度

• 在已经排好序的列表中查询某个数据项 O(logn)

• 在未排好序的列表中查询某个数据项 O(n)

• hash 表的插入，查询与删除 O(1)

  // js
  obj = {a: 1, b: 2}
  obj['a'] // O(1)
  
  var map = new Map();
  map.set('a', 1) // O(1)
  map.get('a') // O(1)
  
  // php
  $arr = ['a' => 1, 'b'  => 2]
  $arr['a'] // O(1)
  
  

空间复杂度

类似于时间复杂度的讨论，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度

通常在递归的时候需要考虑空间复杂度，其中涉及到一个尾调用的概念，就是指某个函数的最后一步是调用另一个函数，这样可以只需存储当前栈的信息，可以极大减少空间复杂度。
尾递归指某个函数的最后一步是调用自身，ES6 的尾调用优化只在严格模式下开启，正常模式是无效的

• 尾调用

// 情况一
function f(x){
  return g(x);
}

// 情况二
function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}

• 非尾调用

// 情况一
function f(x){
  let y = g(x);
  return y;
}

// 情况二
function f(x){
  return g(x) + 1;
}

例子

• 非尾递归的 Fibonacci 函数

function Fibonacci (n) {
  if ( n <= 1 ) {return 1};

  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(100) // 无法计算

• 尾递归的 Fibonacci 函数

function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
  if( n <= 1 ) {return ac2};

  return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}

Fibonacci2(100) // 秒出

尾调用优化