10.算法分析

算法時間復雜度和空間復雜度

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

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

3. 大O表示法：

   參考《算法導論》的列子：考慮計算一個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]    # 注意這里和上邊的不同

兩種方式的主要區別在最后一行，

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

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

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

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

4. 如何計算時間復雜度

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

① 2n * n = 2n²

② n+n*n = n+n²

當n非常大的時候，n*n(即n的平方)的數值將占主導，可以忽略單個n的影響：

n+n²<= 2n²

可以認為兩個算法的時間復雜度都為O(n²)

5.常用的時間復雜度

列舉一些常用的時間復雜度，按照增長速度排序，日常我們的業務代碼中最常用的是指數之前的復雜度，指數和階乘的增長速度非常快， 當輸入比較大的時候用在業務代碼里是不可接受的。

6.空間復雜度

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

常見的空間復雜度的增長趨勢圖：

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