琉璃蘿莎 2019-12-15

#a i從0迴圈到n，演算法複雜度為O（n）。

#b 一共要做n^2/2次加法，演算法複雜度為O（n^2）。

#c 要求一個k，滿足2^k>=n ，演算法複雜度為O（log（n））

#d 注意到這個函式做的事跟#c的函式恰好相反，演算法複雜度相同，也是O（log（n））

#e 因為已算出#g每次做3（n-3）次加法，那麼i從1到n，一共做2/3*（n^2-5n+6）次加法，所以複雜度為O（n^2）。

#f 這個函式可以寫成公式T（n）=T（n-2）+T（n-1），這個遞迴式跟黃金分割有關係，解這個遞迴式，可以知道 T（n） = O（（√5-1/2）^n）

#g 函式呼叫一共做3（n-3）次加法，所以複雜度為O（n）

PenitentSin 這位兄臺的#c 算的不對啦，#g也不對。還有#f，這個雖然是遞迴，但不是遞迴就等於指數級的複雜度，要解遞迴方程才能斷定的。

關於演算法複雜度，《演算法導論》一書中第四章有一個主定理，記住這個定理之後，這些問題就小case了（除了複雜遞迴之外）。