算法時間複雜度和空間複雜度
- 了解時間複雜度對算法的選用會很有幫助，比如說之前怎麼樣選擇資料結構，都是通過每個操作的時間複雜度的分析來看是不是滿足需求，肯定的是，在滿足需求的情況下，時間複雜度越優越好，操作次數越少越好。
- 大O是什麼？可以了解為操作次數與資料個數的比例關系；O(1)是有限次數的操作；O(n)是操作正比于你的元素。
-
大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 = 2n2
② n+n*n = n+n2
當n非常大的時候，n*n(即n的平方)的數值将占主導，可以忽略單個n的影響：
n+n2<= 2n2
可以認為兩個算法的時間複雜度都為O(n2)
5.常用的時間複雜度
列舉一些常用的時間複雜度，按照增長速度排序，日常我們的業務代碼中最常用的是指數之前的複雜度，指數和階乘的增長速度非常快， 當輸入比較大的時候用在業務代碼裡是不可接受的。
| O | 名稱 | 舉例 | 補充 |
| 1 | 常量時間 | 一次指派 | nlogn以下的這些時間複雜度都是比較占優勢的。 |
| logn | 對數時間 | 折半查找 | |
| n | 線性時間 | 線性查找 | |
| nlogn | 對數線性時間 | 快速排序 | |
| n2 | 平方 | 兩重循環 | 越向上增長的越快那那怕是計算機非常快，依然要花很多時間運作。 |
| n3 | 立方 | 三重循環 | |
| 2n | 指數 | 遞歸求斐波那契數列 | |
| n! | 階乘 | 旅行商問題 |
| O(1) | 固定時間内的一次操作，比如:一次指派，一次加法，幾次加法操作。 |
| O(logn) | 二分查找，操作一個有序數組的時候，每次都可以把它折半。 |
| O(n) | 查找都需要從頭查到尾，找到了才能退出。 |
| O(nlogn) | 快速排序或歸并 |
| O(n2) | 兩重循環嵌套 |
| O(n3) | 三重嵌套 |
| O(2n) | 指數就有一些遞歸算法，沒有優化的遞歸 |
| O(n!) | 旅行商問題，學術界讨論會比較多，工程會少一些 |
6.空間複雜度
相比于時間，空間很多時候，不是主要的考慮因素，使用者老爺們都等不及，而且現在存儲都越來越便宜了，為了提升響應速度，能可多用一點空間，是以空間複雜度讨論的少一些；當然，如果資料量非常非常大，也會考慮空間占用的問題。
常見的空間複雜度的增長趨勢圖：