所属分类数据

前言

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

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

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

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

评估标准

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

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

大O表示法

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

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

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

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

时间复杂度

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

估算形式

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

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

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

常见量级

【】表示可能的执行次数

常量阶 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) 取最大量级