時間復(fù)雜度
常數(shù)時間的操作：一個操作和數(shù)據(jù)量沒關(guān)系 ，每次都是固定時間內(nèi)完成的操作，叫做常數(shù)操作
時間復(fù)雜度：算法流程中常數(shù)操作數(shù)量的指標(biāo)，在常數(shù)操作數(shù)量的表達(dá)式中，只要高階項不要低階項，去掉高階項的系數(shù)，即O(f(N))
評價算法：先看時間復(fù)雜度指標(biāo)，然后看實際運行時間，即常數(shù)項時間
時間復(fù)雜度舉例：
以上算法復(fù)雜度以此為O(MN)、O(M*logN)、O(M*logM)+O(M+N)
二分：不斷對半分
外排：兩個都有序，兩個指針誰小移動誰
對數(shù)器
準(zhǔn)備二叉樹，數(shù)組的隨機(jī)樣本發(fā)生器，以及對數(shù)器模板（甚至堆的模板，排序的模板）
冒泡排序（一般不用了）
每次冒泡出來一個最大的放后面，時間復(fù)雜度O(N^2)，額外空間復(fù)雜度O(1)，因為只需要額外幾個變量就可以完成排序，如果是額外申請一個數(shù)組那么額外空間復(fù)雜度為O(N)
選擇排序（一般不用了）
每次選最小的放前面，時間復(fù)雜度O(N^2)，額外空間復(fù)雜度O(1)
插入排序（類似撲克牌插牌）
先排0-1，再排0-2，...新來的數(shù)選合適的位置插入，直到全部排完，此時和數(shù)據(jù)狀況有關(guān)系
最好情況：有序情況，O(N)
最差情況：逆序情況，O(N^2)
一律按最差的情況估計算法，所以時間復(fù)雜度O(N^2)，額外空間復(fù)雜度O(1)
遞歸
以數(shù)組中找最大值為例
遞歸理解：系統(tǒng)幫你壓棧，所以任何遞歸行為都可以改為非遞歸
估計復(fù)雜度的通式：T(N)=aT(N/b)+O(N^d)
滿足上述通式有直接得到時間復(fù)雜度的結(jié)論：
歸并排序
先左側(cè)排序，再右側(cè)排序，最后用外排的方式統(tǒng)一（誰小就用誰并移動指針），T(N)=2T(N/2)+O(N)
時間復(fù)雜度O(N*logN)，額外空間復(fù)雜度O(N)
小和問題和逆序?qū)栴}
①這樣寫防止溢出
②位運算比算術(shù)運算快
