前言

我们通常检验代码的方式采用单元测试的形式，经过实际的代码运行来判断代码有无问题。

这种方式也可以统计运行效率（打印执行时间差），被称为过后统计法，存在以下以下问题：

• 测试结果很是依赖测试环境（不同内存、内核的环境效率有所差异）
• 测试结果受数据规模的影响很大（少量数据和大量数据所得到的结果往往不尽相同）

因此我们需要一种无需执行代码或具体测试的方式，能够粗略地估计算法的执行效率的方法。

评估标准

评估一个方法（算法）的优劣，一般从以下维度：

1. 正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
2. 时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）
3. 空间复杂度（space complexity）：估算所需占用的存储空间

大 O 表示法

公式：T(n) = O(f(n))

• n：表示数据规模的大小
• T(n)：表示代码执行的时间
• f(n)：表示每行代码执行的次数总和
• O：表示代码的执行时间 T(n) 与 f(n) 表达式成正比

大 O 复杂度表示方法只是表示一种变化趋势。

当 n （基数）很大时，公式中的低阶、常量、系数三部分并不左右增加趋势，因此能够忽略。

时间复杂度

时间复杂度的全称是渐进时间复杂度（time complexity），表示算法的执行时间与数据规模之间的增长关系。

估算形式

大 O 复杂度表示方法是一种估算方式，因此在进行估算时无需对全部代码进行阅读。

有三种形式和方式用于参考：

1. 关注循环执行次数最多的一段代码
2. 总复杂度等于量级最大的那段代码的复杂度
3. 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见量级

【】表示可能的执行次数

• 常量阶 O(1)：【13】并非执行一次，代码的执行时间不随 n 的增大而增长
• 对数阶 O(logn)：【3_log_2_n+25】
• 线性阶 O(n)：【8n+8】
• 线性对数阶 O(nlogn)：【6n+3n_log_3_n+90】
• 指数阶 O(2^n) ：【2^n】
• 阶乘阶 O(n!)：【1x2x3x...x(n-1)xn】
• 平方阶 O(n^2) ：【n^2+3n+3】
• 立方阶 O(n^3) ：【2n^3】
• k 次方阶 O(n^k) ：【7n^k】

估算举例

逐行代码列举。

// 假设每行代码执行时间 T
func cal(int n){
    int sum = 0 // 1T
    for i:=0;i<=n;i++ { // 1T + nT + nT
        sum = sum + i; // nT
    }
}
// 总执行时间 (3n+2)*T 
// 大O表示：T(n) = O(3n+2) 
// 忽略常量：T(n) = O(n)
​

前文提到，大 O 是一种估算，对于常量可以忽略。

func cal(int n){
    int sum = 0;// 忽略
    for i:=1;i<=n;i++ { // 关注循环次数
        for j:=1;j<=n;j++ { // 外循环 * 内循环 = n^2
            sum = sum + i*j // 忽略
        }
    }
}
// 大O表示：T(n) = O(n2)
​

多个循环取最大。

func cal(int n) {
    int sum := 0
    for i:=0; i < n; i++) {
        sum += i // O(n)
    }
    for j:=1; j< n {
        j = j * 3 // O(log-3-n) => O(logn)
    }
    for x:=1;x<=n;x++ { 
        for y:=1;y<=n;y++ {
            sum = sum + x*y // O(n^2)
        }
    }
}
// 大O表示：T(n) = O(n2) 取最大量级
​

空间复杂度

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

空间复杂度的估算相比时间复杂度要简单，主需要关心申请内存的空间和次数。

因此，O(logn)、O(nlogn) 对数阶复杂度基本上用不到。

常见量级

• 常量阶 O(1)：【13】
• 线性阶 O(n)：【8n+8】
• 平方阶 O(n^2) ：【n^2+3n+3】
• k 次方阶 O(n^k) ：【7n^k】