複雜度分析

1.空間複雜度
主要是看變動空間，有結構型參數且採call-by-value，或是recursion所需要的stack空間
—>若是recursive，compiler要考慮stack
a.參數
b.區域變數$$x = y$$
c.返回位址

2.時間複雜度—>記住公式:
1.$$\sum i^{d} = n^{d+1}$$
2.$$\sum{i=1}^{n}\frac{1}{i} = log(n)$$
3.$$n!$$約等於$$n^{n+\frac{1}{2}}\times e^{-n}$$
—>要分析程式碼的複雜度，可以
1.邏輯歸納分析
2.化為數學式
—>計算若太複雜，logic跑
—>漸進符號
1.Big O
若f(x)=O(g(x))，則表示存在常數c>0, $$n{0}$$使所有$$n\geq n{0}$$，滿$$f(n)\leq c*g(n)$$
2.注意的是，little-oh與little-omega的定義是：所有c，皆存在$$n{0}$$使得$$f(n) < cg(n),\forall n\geq n{0}$$
—>Recursive Time Function
1.展開代入法
—>切記，若遇到一些特別的，不一定要T(1) = 1，可以是T(2) = 2，使log得以做下去。
2.Master Theory
—>三種case，ε>0
a.$$f(n)=O(n^{log{a}^{b}} -\varepsilon )$$,此處ε>0之正常數
b.$$f(n)=\Theta (n^{log{a}^{b}} )$$
c.$$f(n)=O(n^{log{a}^{b}} +\varepsilon )$$，此處ε>0之正常數，且$$af(\frac{n}{b})\leq f(n)c, c<1 $$
—>Extended
若$$\frac{f(n)}{n^{lon{a}^{b}}} = log^{k}n, k\geq 0$$之正常數，則$$T(n)=\Theta (n^{log{a}^{b}} log^{k+1}n)$$
3.Recursive Tree
—>分兩種:
1.每層的cost皆一樣
—>Θ(每 層的cost*logn)
2.每 層的cost不同，且都小於第一階成本
—>Θ(第一層的cost)
4.近似法當遇到有 斯符號，直接假設沒有
5.給予code求time
—>要求複雜度，不是數學遞迴函數算!
—>ex:若code裡 有return 2*perm(n-1)+1此時複雜度是T(n-1)+即可，不是2T(n-1)+1