算法分析

算法分析就是分析算法占用计算机资源（主要是占用 CPU 时间和内存空间）的多少。

时间复杂度

两种算法时间性能分析

通常有两种衡量算法时间性能的方法，即事后统计法和事前估算法。

事后统计法

事后统计法就是编写算法对于程序，统计其执行时间。但是一个算法用计算机语言实现后，在计算机上执行所消耗的时间与很多因素有关，如使用的语言、编译产生的机器语言代码质量等。

所以事后统计法拥有两个缺点，一是必须执行程序，二是存在很多因素掩盖了算法的本质。

事前估算法

事前估算法憋开这些与计算机硬件、软件有关的因素，仅考虑算法本身的效率高低，可以认为一个特定算法的“运行工作量”的大小只依赖于问题的规模。因此目前主要采用事前估算法来分析算法的时间性能。

时间复杂度分析

计算算法的频度 T(n)

一个算法是由控制结构（顺序、分支和循环）和原操作（指固有的数据类型的操作）构成。如下：

function fun(n) {
    let i;  //原操作
    let sum = 0;  //原操作
    for(i=0; i<n; i++) { // 这里也有 3 个原操作
        sum = sum + i //原操作
    }
    return i; //原操作
}

而算法的执行时间取决于控制结构和原操作的综合效果。显然，在一个算法中执行原操作的次数越少，其执行的时间也就相对越少；执行原操作次数越多，其执行时间也就相对越多。也就是说，一个算法的执行时间可以由其中原操作的执行次数来计算。

假设算法的问题规模为 n。算法时间分析就是求出算法所有原操作的执行此时，它是问题规模 n 的函数，用 T(n)表示。

那么上述例子的 T(n) 为 1 + 1 + 1 + (n+1) + n + n + 1

function fun(n) {
    let i;  // 1
    let sum = 0;  // 1
    for(i=0; i<n; i++) { // 1 + (n+1) + n
        sum = sum + i // n
    }
    return i; // 1
}

T(n) 用 "O" 表示

由于算法分析不是绝对时间的比较，在求出 T(n) 后，通常进一步采用时间复杂度来表示。算法时间复杂度就是用 T(n) 的数量级来表示，记作 T(n) = O(f(n))。

T(n)变成 O 的规则:

• 去掉常数
• 去掉低阶
• 去掉系数

所以上述例子的时间复杂度为 O(n)

常用的时间复杂度

O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2) （平方阶）、O(n^3)（立方阶）、O(2^n)（指数阶）

其从小到大的顺序关系如下： O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

空间复杂度

算法空间复杂度分析

一个算法的存储量包括输入数据所占的空间，程序本身所占的空间和临时变量所占的空间。这里在对算法进行存储空间分析只考察临时变量所占的空间。

function max(let arr[]) {
    let i, max = 0
    for(i=0;i<arr.length;i++) {
        if(arr[i] > arr[max])
        max = i
    }
    return arr[max]
}

就像上面的临时变量只有 i 和 max 为 1，所以空间复杂度就为 O(1)。

TIP

空间复杂度和时间复杂度一样都会去除常数、低阶和系数