10.算法分析

算法時(shí)間復(fù)雜度和空間復(fù)雜度

1. 了解時(shí)間復(fù)雜度對算法的選用會很有幫助，比如說之前怎么樣選擇數(shù)據(jù)結(jié)構(gòu)，都是通過每個操作的時(shí)間復(fù)雜度的分析來看是不是滿足需求，肯定的是，在滿足需求的情況下，時(shí)間復(fù)雜度越優(yōu)越好，操作次數(shù)越少越好。

2. 大O是什么？可以理解為操作次數(shù)與數(shù)據(jù)個數(shù)的比例關(guān)系；O(1)是有限次數(shù)的操作；O(n)是操作正比于你的元素。

3. 大O表示法：

   參考《算法導(dǎo)論》的列子：考慮計(jì)算一個n * n的矩陣所有元素的和：

 列舉兩種方式：

# version1
total_sum = 0
for i in range(n):
    row_sum[i] = 0
    for j in range(n):
        row_sum[i] = row_sum[i] + matrix[i, j]
        total_sum = total_sum + matrix[i, j]

# version2
total_sum = 0
for i in range(n):
    row_sum[i] = 0
    for j in range(n):
        row_sum[i] = row_sum[i] + matrix[i, j]
    total_sum = total_sum + row_sum[i]    # 注意這里和上邊的不同

兩種方式的主要區(qū)別在最后一行，

    第一個方式：假設(shè)矩陣是n*n的，這嵌套是在兩層循環(huán)里面，而且每一步都循環(huán)n次，可以認(rèn)為它是一個n*n的，循環(huán)兩次，即 (2n)*n的時(shí)間復(fù)雜度。

    第二個方式：假設(shè)矩陣是n*n的，能看出最后一行不在上面的循環(huán)里面，上面的循環(huán)執(zhí)行了n*n(嵌套在兩層循環(huán)里面)，最后一行是執(zhí)行n次，所以他是n*n+n的時(shí)間復(fù)雜度。

如果數(shù)據(jù)量很小，可能感覺不出差異，但是如果放大n的增長的時(shí)候，總的操作次數(shù)就很明顯區(qū)別了：

通常不關(guān)系每個算法執(zhí)行了多少次，更關(guān)心隨輸入規(guī)模的增加算法運(yùn)行的時(shí)間將以什么樣的速度增加，所以定義了一個符號，大O符號。

4. 如何計(jì)算時(shí)間復(fù)雜度

上面舉例2個版本的計(jì)算矩陣和的代碼，有兩個公式：

① 2n * n = 2n²

② n+n*n = n+n²

當(dāng)n非常大的時(shí)候，n*n(即n的平方)的數(shù)值將占主導(dǎo)，可以忽略單個n的影響：

n+n²<= 2n²

可以認(rèn)為兩個算法的時(shí)間復(fù)雜度都為O(n²)

5.常用的時(shí)間復(fù)雜度

列舉一些常用的時(shí)間復(fù)雜度，按照增長速度排序，日常我們的業(yè)務(wù)代碼中最常用的是指數(shù)之前的復(fù)雜度，指數(shù)和階乘的增長速度非?？?， 當(dāng)輸入比較大的時(shí)候用在業(yè)務(wù)代碼里是不可接受的。

6.空間復(fù)雜度

    相比于時(shí)間，空間很多時(shí)候，不是主要的考慮因素，用戶老爺們都等不及，而且現(xiàn)在存儲都越來越便宜了，為了提升響應(yīng)速度，能可多用一點(diǎn)空間，所以空間復(fù)雜度討論的少一些；當(dāng)然，如果數(shù)據(jù)量非常非常大，也會考慮空間占用的問題。

常見的空間復(fù)雜度的增長趨勢圖：

所以，工程上能接受的都是 nlogn 以下的空間復(fù)雜度，圖中nlogn，n，log2n這些。