复杂度

算法的五要素

输入、输出
可行性
正确性
确定性
有穷性

时间复杂度

为了测试算法的运行效率，我们可以在机器上跑一些测试数据，来测试算法具体执行时间的快慢，这叫做 事后统计法，但是， 事后统计法有下面两个缺点：

执行效率受到 运行环境 的影响，两台不同的机器可能的到相反的结果
执行效率受到输入的 测试数据规模 的影响

所以，为了发现 数据规模 和 运行效率 之间的关系，引入了 复杂度分析

渐进时间复杂度分析

所谓渐进时间复杂度，即为表示 算法执行时间效率与输入规模 n 增长时的趋势，使用函数来描述 n 增长时，运行效率的变化趋势。

使用大 O 记号来表示时间复杂度：
如果存在 f(n)，使得在 n >> 2 的情况下，时间复杂度 T(n) <= Cf(n)，则时间复杂度可以表示为 O(f(n))

大 O 记号有如下特点：

f(n) 函数的 常数项 和 低次幂项 可以省略(应为在 n 具有相当规模时，这些对高次幂的影响不大)
若 T(n) = T1(n) + T2(n)，则 T(n) = O( max( f(n), g(n) ) )
若 T(n) = T1(n) * T2(n)，则 T(n) = O( f(n)*g(n) )
若有两个输入时，若 T(n) = T1(n) + T2(m)，则 T(n) = O( f(n) + g(m) )
若有两个输入时，若 T(n) = T1(n) * T2(m)，则 T(n) = O( f(n)*g(m) )

常见时间复杂度

对于时间复杂度，基本可以分为两类，多项式量级 和 非多项式量级，而非多项式量级有两个：O(2ⁿ)、O(n!)

常见时间复杂度：

常量阶： O( 1 )
对数阶： O( log(n) )
线性阶： O( n )
线性对数阶： O( nlog(n) )
幂次阶： O( n^k ) (k = 2,3,4...)

O(1)

O(1) 不是指只有一条语句执行，而是只要执行的语句是确定个数的，和输入规模 n 没有关系的，都是 O(1) 复杂度

一般来讲，只要代码中没有循环、递归，基本都是 O(1) 复杂度的

O(n)、O(nlog(n))

对数阶复杂度比较常见，也是比较难分析的
例：

let i = 0;
let sum = 0;
while(i < n){
  sum += i;
  i += 2;
}

上面这段代码，i 每次都加 2，所以最后等于 n 的时候， 2^x = n，所以 x = log₂n，由于底数之间可以互相转化，所以忽略底数，记做 log(n)

O( nlog(n) ) 则是相当于把 O( log(n) )的算法执行了 n 次，根据大 O 记号的乘法原理，则复杂度就为 O( nlog(n) )

空间复杂度

空间复杂度指的是，算法运行过程中新申请的空间占用，算法必须使用的空间占用不计入其中

时间复杂度例子

1. O(1)

// 从 n >= 3 的数组中找一个非最大、最小数
// 解决该问题一共有三步
// 1. 选取任意数组中三个数
// 2. 对选取的数进行排序
// 3. 输出排序结果的第二个数

这里的执行时间和 n 无关，只限于有限步骤，所以时间复杂度为 O(1)

2. O( log(n) )

// 输出给定非负整数的二进制的 1 的个数
function count(n){
  let count = 0;
  while(n!=0){
    sum += n & 1;
    n >>= 1;
  }
}

使用右移运算符，n 每次都减少一半，所以有： 2^x = n，x = log(n)，所以一共执行了 1 + x 轮循环，所以时间复杂度为 O( log(n) )

3. O( n )

// 计算数组和
function sum(arr){
  let sum = 0;
  for(let i=0; i<arr.length; i++){
    sum += arr[i];
  }
}

计算和的时候，根据数组长度 n，一共执行了 n 次加法操作，所以时间复杂度为 O( n )

4. O( nlog( n ) )

// 归并排序
function mergeSort(arr){
  if(arr.length === 1){
    return arr;
  }
  mergeSort(left, middle);
  mergeSort(middle+1, right);
  merge(left, middle, right);
}

分析1：
根据代码得出时间复杂度公式：T(n) = 2*T(n/2) + O(n)，T(1) = O(1)，则推出 T(n) = nO(1) + n/2*O(2) + n/4*O(4) + ... + 2*O(n/2) + O(n)，其中个数为 log(n) 个，所以时间复杂度为 O( nlog( n ) )

分析2：
递归一共生成了 n + n/2 + n/4 + ... + 1 个递归实例，其中个数为 log(n) 个，所以总个数为 C*nlog(n)，所以时间复杂度为 O( nlog( n ) )

复杂度