大O，大
,大
大O
大O表示一個函數(shù)f(x)在大于某一個數(shù)時荸频，存在一個正數(shù)戏仓，使得
存在疚宇，即函數(shù)的上界函數(shù)
大
大O表示一個函數(shù)f(x)在大于某一個數(shù)時，存在一個正數(shù)c柜去，使得存在灰嫉，即函數(shù)的下界函數(shù)
大
當一個函數(shù)的上下界函數(shù)相等時（c可不相等）
遞歸方程階的計算
大膽猜測小心求證（先猜拆宛，再數(shù)學歸納法證明）
暴力求解
將遞歸方程暴力分解嗓奢，直到括號內(nèi)與1同階為止
例? ?
令，即
則
Master定理（具有局限性）
用于解決形如的遞歸方程股耽，比較
與
階的關(guān)系
二者取較大者為該遞推方程的階
若二者相等，則在階上乘為遞推方程的階
例
所以
分治算法
將問題分解成多個小問題钳幅，降低問題的規(guī)模
最大子數(shù)組
最大子數(shù)組有三種情況構(gòu)成物蝙，一種位于中間數(shù)的左側(cè)，一種位于中間數(shù)的右側(cè)敢艰，最后一種跨越了中間數(shù)诬乞。在這之中，位于左側(cè)和右側(cè)這兩種情況的子問題與最大子數(shù)組相同钠导，所以關(guān)鍵就是尋找跨越中間數(shù)的最大子數(shù)組震嫉。
而跨越的最大組數(shù)組可由單側(cè)的最大子數(shù)組相加求得。
cross-mid( A,begin,end)
mid=(bigin+end)/2
for i mid downto begin
sum+=A[i]
if sum > left-sum
left-sum=sum
max-left=i
//右側(cè)同理
return （max-left, max-right, left-sum+right-sum)
最終代碼
max(A,begin,end)
if begin=end
return (begin,end,A[begin])
mid=(begin+end)/2
(left-begin,left-end,left-max)=max(A,begin,mid)
(right-begin,right-end,right-max)=max(A,mid+1,end)
(mid-begin,mid-end,mid-max)=cross-mid(A,begin,end)
//不可由上兩個式子形成牡属，因為左右兩側(cè)的最大子數(shù)組不一定包括中間數(shù)
max(mid-max,left-max,right-max)
return//上式對應的
歸并排序
不斷二分到只剩一個數(shù)字（）進行歸并票堵，用一個空的與原數(shù)組等長數(shù)組來做中介排序，返回排好序的數(shù)字
//再排序過程中如果計數(shù)調(diào)整順序的次數(shù)逮栅，則將此題派生為求逆序?qū)€數(shù)
矩陣乘法
兩個n階矩陣相乘則結(jié)果矩陣中元素的值為
所以傳統(tǒng)矩陣相乘的時間復雜度為
若將矩陣分為四個n/2階的小矩陣
? ? ? ? ?
? ? ? ? ?
此時時間復雜度為時間復雜度并沒有改變
此時時間復雜度為時間復雜度減小了
大整數(shù)乘法
當兩個長度為N的大整數(shù)相乘悴势，一般情況下需要消耗的時間復雜度，是否可以利用分治降低時間復雜度措伐？
則
此時,時間復雜度為
時間復雜度并沒有發(fā)生改變
倘若我們稍稍改動特纤，j減少相乘，增加加減侥加，盡多的利用已有的結(jié)果
此時,時間復雜度為
第K小元素
動態(tài)規(guī)劃
與分治法類似叫潦，動態(tài)規(guī)劃也是將問題劃分為更小的問題進行解決，但區(qū)別在于，子問題是具有重復性的矗蕊，這將大大減小時間復雜度
動態(tài)規(guī)劃條件
最優(yōu)子結(jié)構(gòu)
當一個問題的最優(yōu)解包含了子問題的最優(yōu)解時短蜕，稱這個問題具有最優(yōu)子結(jié)構(gòu)
證明時是用反證法
重疊子問題
一個子問題的解在求解中不斷被利用
矩陣連乘
最優(yōu)子結(jié)構(gòu)證明
若m[i,j]表示Ai...Aj相乘時最少的乘法次數(shù)，m[j+1,k]表示Aj+1...Ak相乘時最少的乘法次數(shù)
則m[i,k]=m[i,j]+m[j+1,k]+ri×rj×rk
重疊子問題證明
所以構(gòu)建二維矩陣m[i,j]用于存儲某個區(qū)間內(nèi)矩陣相乘最少的乘法次數(shù)傻咖，i表示開始的矩陣下標朋魔，j表示結(jié)束的矩陣下標
鋼條切割
最優(yōu)子結(jié)構(gòu)
當最終是最大收益時，切割下來的每一部分也是當前長度的最大收益
重疊子問題
最長公共子序列
二維矩陣m[i,j]表示Xi和Yj中最長公共子序列的長度
m[i,j]=1/0,? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?i=j
m[i,j]=m[i-1,j-1]+1,? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? X[i]=Y[j]
m[i,j]=max{m[i-1,j],m[i,j-1]},? ? ? ? ? ? ? i≠j卿操，X[i]≠Y[j]
0/1背包問題
背包中物品只可整個裝入或者取出警检，不可部分裝入取出
dp[i][j]表示物品為i，i+1害淤，...扇雕，n，背包容量為j時的最優(yōu)解
dp[i][j]=dp[i+1][j]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? j<pi??
dp[n][j]=0? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?j=0
dp[n][j]=pn? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?j≥vn
貪心算法
活動選擇問題（ 最少圓覆蓋最多點）
選擇活動結(jié)束時間最早的活動窥摄，下一個活動為開始時間比現(xiàn)有活動晚且結(jié)束時間最早的活動镶奉。
