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

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

大O復雜度表示法

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

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

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

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

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

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

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

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

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

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í)行時間T(n) 與 f(n)表達式成比例。

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

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

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), 另一個 T(n) = O(2n2 + n + 1)，用大O表示法表示上面兩段代碼的時間復雜度，可以記為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í)行指令數，10*n2

對比上面兩個算法，當 n = 10, n=100 時， 算法B執(zhí)行的速度更快，n = 1000 時兩者速度相當

                                        隨著數據規(guī)模的進一步增大， 這個差距會越來越大

時間復雜度分析

如何分析一段代碼的時間復雜度?

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

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

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

總復雜度等于量級最大的那段代碼的復雜度

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，計算sum_部分的代碼段時間復雜度O(n)，計算sum_1部分的代碼段時間復雜度為O(n2) ，總的時間復雜度由復雜度最大的部分決定, 所以上面代碼復雜度為O(n2)。

嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積

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_

上面的代碼中第二個函數調用了第一個函數, 如果把fn函數調用當作一個普通操作, 那么第二個函數的時間復雜度為O(n) Fn函數的時間復雜度為O(n)，那么函數整體的時間復雜度為O(n*n) = O(n2)。

當兩段代碼的數據規(guī)模不同時，不能省略復雜度低的部分

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，計算sum_部分的代碼段時間復雜度O(n)，計算sum_1部分的代碼段時間復雜度為O(m2) ，總的時間復雜度由復雜度最大的部分決定, 所以上面代碼復雜度為O(m2+n)