如何分析一段代碼的復(fù)雜度？【算法面試題】

復(fù)雜度分析是估算算法執(zhí)行效率的方法，公式O(f(n))表示算法的復(fù)雜度，此方法即為大O復(fù)雜度表示法O(f(n))中n表示數(shù)據(jù)規(guī)模，f(n)表示運(yùn)行算法所需要執(zhí)行的指令數(shù)。

大O復(fù)雜度表示法

下面的代碼非常簡單,求 1,2,3…n 的累加和，我們要做的是估算它的執(zhí)行效率。

def calc(n):
    sum_ = 0
    for i in range(1，n+1):
        sum_ = sum_ + i
    return sum_

假設(shè)每行代碼執(zhí)行的時(shí)間都一樣為t，執(zhí)行第2行代碼需要時(shí)間t，第3,4行代碼運(yùn)行了n遍，需要的時(shí)間為2n*t，這段代碼總執(zhí)行時(shí)間為(2n+1)* t

結(jié)論：代碼執(zhí)行的總時(shí)間T(n)與每行代碼的執(zhí)行次數(shù)成正比

看下面的代碼，估算該段代碼的執(zhí)行時(shí)間:

def calc(n):
    sum_ = 0
    for i in range(n):
        for j in range(n):
            sum_ = sum_ + i*j
    return sum_

同樣假設(shè)每行代碼執(zhí)行的時(shí)間都一樣為t：執(zhí)行第2行代碼需要時(shí)間t，第3行代碼運(yùn)行了n遍，需要時(shí)間為n*t，第4、5行代碼運(yùn)行了n2次，需要時(shí)間為2n2 * t，執(zhí)行所有代碼的總時(shí)間為 (2n2 + n + 1)* t。

結(jié)論：代碼執(zhí)行的總時(shí)間T(n)與每行代碼的執(zhí)行次數(shù)成正比。

用O(f(n))來表示算法復(fù)雜度：

def calc(n):
    sum_ = 0
    for i in range(1，n+1):
        sum_ = sum_ + i
    return sum_

def calc(n):
    sum_ = 0
    for i in range(n):
        for j in range(n):
            sum_ = sum_ + i*j
    return sum_

T(n) = O(f(n)) , O表示代碼的執(zhí)行時(shí)間T(n) 與 f(n)表達(dá)式成比例。

大O復(fù)雜度表示法：上面例子中的T(n) = O(2n+1), 另一個(gè) T(n) = O(2n2 + n + 1)。大O時(shí)間復(fù)雜度并不表示代碼真正的執(zhí)行時(shí)間，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長的變化趨勢(shì)，也叫作漸進(jìn)時(shí)間復(fù)雜度(asymptotic time complexity)，簡稱時(shí)間復(fù)雜度。

當(dāng)數(shù)據(jù)量特別大， 也就是n的取值很大的時(shí)候，大O表示法中低階、常量、系數(shù)三部分并不會(huì)左右增長趨勢(shì)，可以忽略。

def calc(n):
    sum_ = 0
    for i in range(1，n+1):
        sum_ = sum_ + i
    return sum_

def calc(n):
    sum_ = 0
    for i in range(n):
        for j in range(n):
            sum_ = sum_ + i*j
    return sum_

上面例子中的T(n) = O(2n+1), 另一個(gè) T(n) = O(2n2 + n + 1)，用大O表示法表示上面兩段代碼的時(shí)間復(fù)雜度，可以記為O(n)，O(n2)。

算法A： O(n) 執(zhí)行指令，10000*n

def calc(n):
    sum_ = 0
    for i in range(1，n+1):
        sum_ = sum_ + I
  """
  此處省略n行... ...
  """
    return sum_

算法B： O(n2) 執(zhí)行指令數(shù)，10*n2

對(duì)比上面兩個(gè)算法，當(dāng) n = 10, n=100 時(shí)， 算法B執(zhí)行的速度更快，n = 1000 時(shí)兩者速度相當(dāng)

                                        隨著數(shù)據(jù)規(guī)模的進(jìn)一步增大， 這個(gè)差距會(huì)越來越大

時(shí)間復(fù)雜度分析

如何分析一段代碼的時(shí)間復(fù)雜度?

在分析一個(gè)算法、一段代碼的時(shí)間復(fù)雜度時(shí)，只關(guān)注循環(huán)執(zhí)行次數(shù)最多的那一段代碼就可以了。

def calc(n):
    sum_ = 0
    for i in range(n):
        for j in range(n):
            sum_ = sum_ + i*j
    return sum_

上面的代碼中，我們只需要關(guān)注內(nèi)層for循環(huán)的時(shí)間復(fù)雜度就可以了，內(nèi)層for循環(huán)的兩行代碼被執(zhí)行了n2次，所以總的時(shí)間復(fù)雜度就是O(n2)

總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜度

def calc(n):
sum_ = 0
    for i in range(1，n+1):
        sum_ = sum_ + i
    sum_1 = 0
    for i in range(1,n+1):
        for j in range(n):
            sum_1 = sum_1 + i*j
    return sum_+sum_1

上面的代碼分為兩部分，分別是求 sum_、sum_1，計(jì)算sum_部分的代碼段時(shí)間復(fù)雜度O(n)，計(jì)算sum_1部分的代碼段時(shí)間復(fù)雜度為O(n2) ，總的時(shí)間復(fù)雜度由復(fù)雜度最大的部分決定, 所以上面代碼復(fù)雜度為O(n2)。

嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積

def fn(n):
    sum_ = 0
    for i in range(n+1):
        sum_ = sum_ + i
    return sum_
def calc(n):
    sum_ = 0
    for i in range(n+1):
        sum_ = sum_ + fn(i)
    return sum_

上面的代碼中第二個(gè)函數(shù)調(diào)用了第一個(gè)函數(shù), 如果把fn函數(shù)調(diào)用當(dāng)作一個(gè)普通操作, 那么第二個(gè)函數(shù)的時(shí)間復(fù)雜度為O(n) Fn函數(shù)的時(shí)間復(fù)雜度為O(n)，那么函數(shù)整體的時(shí)間復(fù)雜度為O(n*n) = O(n2)。

當(dāng)兩段代碼的數(shù)據(jù)規(guī)模不同時(shí)，不能省略復(fù)雜度低的部分

def calc(n):
sum_ = 0
    for i in range(1，n+1):
        sum_ = sum_ + i
    sum_1 = 0
    for i in range(1,m+1):
        for j in range(m):
            sum_1 = sum_1 + i*j
    return sum_+sum_1

上面的代碼分為兩部分，分別是求 sum_、sum_1，計(jì)算sum_部分的代碼段時(shí)間復(fù)雜度O(n)，計(jì)算sum_1部分的代碼段時(shí)間復(fù)雜度為O(m2) ，總的時(shí)間復(fù)雜度由復(fù)雜度最大的部分決定, 所以上面代碼復(fù)雜度為O(m2+n)