算法正確性和復雜度分析

算法正確性——循環不變式

算法復雜度的計算

方法一 代換法

　　—局部代換

　　　　這里直接對n變量進行代換

　　　　—替換成對數或者指數的情形 n = 2^m

　　—整體代換?

　　　　這里直接對遞推項進行代換

　　　　—替換成內部遞推下標的形式 T(2^n) = S(n)

?

方法二 遞歸樹法

　　—用實例說明

　　　　

　　　　—分析每一層的內容

　　　　　　—除了遞歸項的內容拿出來，如第一種樹把T(n-kn)作為下一層進行計算

　　　　　　—遞歸項按層寫出

?

方法三 主定理

　　—f(n)必須是n的多項式規模的才能使用主定理

　　　　—

　　　　—f(n)比較小，那么前面a,b確定的復雜度做主導

　　　　—f(n)和a,b持平，那么是2

　　　　—f(n)比較大，且滿足后面的規則性條件，就以f(n)作為主導

添加次數較小的項

　　—由于不等式方向問題，需要抵消f(n)，需要添加不同次數的項