算法相關(guān)

大O，大\Omega,大\Theta

大O

大O表示一個函數(shù)f(x)在大于某一個數(shù)時，存在一個正數(shù)c，使得f(x)\leq cO(g(x))存在，即函數(shù)的上界函數(shù)

大\Omega

大O表示一個函數(shù)f(x)在大于某一個數(shù)時，存在一個正數(shù)c，使得c\Omega (g(x))\leq f(x)存在，即函數(shù)的下界函數(shù)

大\Theta

當(dāng)一個函數(shù)的上下界函數(shù)相等時（c可不相等）

遞歸方程階的計算

大膽猜測小心求證（先猜，再數(shù)學(xué)歸納法證明）

暴力求解

將遞歸方程暴力分解，直到括號內(nèi)與1同階為止

例? ?T(n)=7T(\frac{n}{7})+n

T(n)=kn+7^kT(\frac{n}{7^k})

令\frac{n}{7^k}=1，即k=\log_7 n

則T(n)=\theta (nlog_7 n)=\theta (nlogn)

Master定理（具有局限性）

用于解決形如T(n)=aT(\frac{n})+f(n)的遞歸方程，比較n^{log_ba}與f(n)階的關(guān)系

二者取較大者為該遞推方程的階

若二者相等，則在階上乘logn為遞推方程的階

例T(n)=7T(\frac{n}{7})+n

\theta (n^{log_77})=\theta (n)

所以T(n)=\theta (nlogn)

分治算法

將問題分解成多個小問題，降低問題的規(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//上式對應(yīng)的

歸并排序

T(n)=2T(\frac{n}{2})+n=\Theta(nlogn)

不斷二分到只剩一個數(shù)字（2\Theta(\frac{n}{2})）進行歸并，用一個空的與原數(shù)組等長數(shù)組來做中介排序，返回排好序的數(shù)字

//再排序過程中如果計數(shù)調(diào)整順序的次數(shù)，則將此題派生為求逆序?qū)€數(shù)

矩陣乘法

兩個n階矩陣相乘則結(jié)果矩陣中元素的值為

c_{ij}=\sum_{k=1}^na_{ik}\cdot b_{kj}

所以傳統(tǒng)矩陣相乘的時間復(fù)雜度為\Theta(n^3)


若將矩陣分為四個n/2階的小矩陣

C_{11}=A_{11}B_{11}+A_{12}B_{21}? ? ? ? ?C_{12}=A_{11}B_{12}+A_{12}B_{21}

C_{21}=A_{21}B_{11}+A_{22}B_{21}? ? ? ? ?C_{22}=A_{22}B_{22}+A_{21}B_{12}

此時時間復(fù)雜度為T(n)=8T(\frac{n}{2})+\Theta(n^2)=\Theta(n^3)時間復(fù)雜度并沒有改變


此時時間復(fù)雜度為\Theta(n^{log_27})時間復(fù)雜度減小了

大整數(shù)乘法

當(dāng)兩個長度為N的大整數(shù)相乘，一般情況下需要消耗\Theta(n^2)的時間復(fù)雜度，是否可以利用分治降低時間復(fù)雜度？


則XY=(A2^{n/2}+B)(C2^{n/2}+D)

XY=AC2^n+ADn^{n/2}+BC2^{n/2}+BD

此時,時間復(fù)雜度為T(n)=4T(n/2)+\Theta(n)=\Theta(n^2)

時間復(fù)雜度并沒有發(fā)生改變

倘若我們稍稍改動，j減少相乘，增加加減，盡多的利用已有的結(jié)果

XY=AC2^n+((A+B)(C+D)-AC-BD)2^{n/2}+BD

此時,時間復(fù)雜度為T(n)=3T(n/2)+\Theta(n)=\Theta(n^{log_23})

第K小元素

動態(tài)規(guī)劃

與分治法類似，動態(tài)規(guī)劃也是將問題劃分為更小的問題進行解決，但區(qū)別在于，子問題是具有重復(fù)性的，這將大大減小時間復(fù)雜度

動態(tài)規(guī)劃條件

最優(yōu)子結(jié)構(gòu)

當(dāng)一個問題的最優(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表示開始的矩陣下標(biāo)，j表示結(jié)束的矩陣下標(biāo)

m[i,j]=min(m[i,k]+m[k+1,j]+ri×rk×rj), i<j

m[i,j]=0, i\geq j

鋼條切割

最優(yōu)子結(jié)構(gòu)

當(dāng)最終是最大收益時，切割下來的每一部分也是當(dāng)前長度的最大收益

重疊子問題


m(n)=\max_{1\leq i\leq n}(p_i+m(n-i))

最長公共子序列

二維矩陣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]=max(dp[i+1][j],dp[i+1][j-p_i]+v_i),j\geq p_i

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é)束時間最早的活動。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容