浅析时间、空间复杂度

2018-12-11 本文已影响3人 Mr_zY

为什么学习复杂度分析

我们将代码跑一遍，通过统计、监控得到算法执行的时间和占用内存的大小，该方法可以称为“事后统计法”。但该方法有其局限性：
1. 测试结果非常依赖环境
  不同硬件环境对结果影响很大。例如：i9和i3的CPU分别运行同一份代码，等到的结果显而易见。
2. 测试结果受数据规模影响很大
  测试数据规模非常小时，测试结果可能无法真实反映算法性能。例如：小规模数据排序时，插入排序可能会比快速排序要快。
所以，我们需要一个不用具体的运行数据来测试，就可以粗略地估计出算法的执行效率的方法。

大O复杂度表示法

算法的执行效率，简单讲就是算法代码的执行时间。大O表示法可以让我们通过观察算法代码直接估算出其执行时间。
下面是一个1,2,3,,,n的累加函数

# 在Python中range函数遵循左闭右开原则，此处需运算1到n的累加和，故为range(1, n+1)
def cal(n):
    sum = 0
    for i in range(1, n+1):
        sum += i
    return sum

我们假设在CPU中每行代码的执行时间都是一样的，用unit_time表示。
第2行代码分别需要1个unit_time的执行时间；第3、4行分别运行n遍，故需要2*n*unit_time的执行时间；第6行代码需要1个unit_time的执行时间。故，该函数总共需要(2n+2)*unit_time的执行时间。通过该公式可以看出，所有代码的执行时间T(n)与每行代码的执行时间成正比。

按照上述分析思路，在看下面一段代码，它的总执行时间T(n)是多少呢？

def cal(n):
    sum = 0
    for i in range(1, n+1):
        print(sum)
        for j in range(1, n+1):
            sum = sum + i * j
    return sum

第1、7行代码需要1个unit_time的执行时间；第2、3行代码分别执行了n遍，需2n*unit_time的执行时间；第4、5行代码分别执行了n*n遍，需2n²*unit_time的执行时间，所以该函数总执行时间T(n) = 2*unit_time + 2n*unit_time + 2n²*unit_time = 2(n²+n+1)*unit_time。
综合两端代码可知，所有代码的执行时间T(n)与每行代码的执行次数n成正比。故得出以下公式：
$T(n) = O(f(n))$

T(n): 代码执行时间
n: 数据规模的大小
f(n): 每行代码执行的次数总和。因为是一个公式，所以用f(n)表示。
O: 表示代码的执行时间T(n)与f(n)成正比，即代码执行时间随数据规模增长的变化趋势

因此，第一段代码中T(n) = O(2n+2)，第二段代码中T(n) = O(2n²+2n+2)。而公式中的低阶、常量、系数三部分并不会左右增长趋势，可以忽略，只需要记录一个最大量级就行。那么用大O表示法表示上面两段代码的时间复杂度，就可以写作：T(n) = O(n)；T(n) = O(n²)

时间复杂度分析

只关注循环次数最多的一段代码

def cal(n):
    sum = 0
    for i in range(1, n+1):
        sum += i
    return sum

第2行代码是常量级的执行时间，与n的大小无关，即对复杂度没影响；第3、4行代码运行了n遍，所以该段代码的时间复杂度为O(n)。

加法法则：总复杂度等于量级最大的那段代码的复杂度

def cal(n):
    sum1 = 0
    for p in range(1, 101):
        sum1 += p
    
    sum2 = 0
    for q in range(1, n+1):
        sum2 += q
    
    sum3 = 0
    for i in range(1, n+1):
        print(sum3)
        for j in range(1, n+1):
            sum3 = sum3 + i * j
    
    return sum1+sum2+sum3

该段代码分为sum1、sum2、sum3三部分。sum1部分代码执行了100遍，为常量级的执行时间（一段代码无论执行了1w次、100w次，只要是已知的数，都是常量级的执行时间）；sum2、sum3部分代码的时间复杂度分别是O(n)，O(n²)。总复杂度等于量级最大的那段代码的复杂度，那么该函数的的复杂度为：O(n²)

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

def cal(n):
    ret = 0
    for i in range(1, n+1):
        ret += f(i)
    return ret

def f(n):
    sum = 0
    for i in range(1, n+1):
        sum += i
    return sum

cal()函数中，先将第4行的f(i)看做常量级操作，那么其时间复杂度为T1(n) = O(n)；但f()也是函数，且它的时间复杂度为T2(n) = O(n)，所以，整个cal()函数的时间复杂度是：T(n) = T1(n) * T2(n) = O(n * n) = O(n²)

几种常见时间复杂度实例分析

复杂度量级（按数量级递增）

常量阶 O(1) ---- 多项式量级

对数阶 O(logn) ---- 多项式量级

线性阶 O(n) ---- 多项式量级

线性对数阶 O(nlogn) ---- 多项式量级

平方阶 O(n²)、立方阶 O(n³)、···、k平方阶 O(n^k) ---- 多项式量级

指数阶 O(2ⁿ) ---- 非多项式量级

阶乘阶 O(n!) ---- 非多项式量级

当数据规模n越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。

O(1)

i = 1
j = 2
sum = i + j

只要代码的执行时间不随n的增大而增长，这样的代码的时间复杂度记作O(1)。一般情况下，只要代码中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度均为O(1)。

O(logn)、O(nlogn)

i = 1
while i <= n:
    i *= 2

变量i从1开始，每循环一次，i乘2，当i大于n时，结束循环。转换成数学公式就是：
$2^1*2^2*···*2^i = n$
所以，只要知道i的值就可以得出代码的执行次数。根据数学知识:2ⁱ = n 得出 i = log₂n，因此这段代码的时间复杂度就是O(log₂n)。并且，对数之间是可以相互转换的，log₃n等于log₃2 * log₂n，所以O(log₃n) = O(C * log₂n)，其中C=log₃2是常量，在大O标记复杂度时可以忽略，即O(Cf(n)) = O(f(n))。因此，在对数阶时间复杂度的表示方法中统一表示为O(logn)。
理解了O(logn)，再结合上面讲的乘法法则。如果一段代码的时间复杂度是O(logn)，我们再将这段代码循环n次，那么，时间复杂度就是O(nlogn)了。O(nlogn)也是一种非常常见的时间复杂度，比如：归并排序、快速排序。

空间复杂度分析

类比时间复杂度，空间复杂度是表示算法的存储空间与数据规模之间的增长关系。

void p(int n){
    int i = 0;
    int[] a = new int[n];
    for (i; i < n; ++i){
        a[i] = i * i
    } 
    
    for (i=n-1; i>=0; --i){
        print out a[i]
    }
}

和时间复杂度分析一样，在第2行中，我们申请了一个空间存储变量i，但他是常量阶的，可以忽略；第3行中，申请了一个大小为n的int类型数组；剩下的代码中都没有占用更多的空间，所以整段代码的空间复杂度为O(n)。常见的空间复杂度有O(1)、O(n)、O(n²)，像O(logn)、O(nlogn)这样的对数阶空间复杂度平时用不到。:smile: