blog as a CSIE student: Big-oh 和 master method

這是今天補習時一直困擾我的兩樣東西

所以乾脆就把東西查查寫寫，以造福後人。

是說如果你不去看英文wiki反而來我這個部落格大概也是走投無路了，那我也就不害羞把有點白癡的想法寫下來了。

補一個還滿詳細的Bog-Oh相關網頁 http://www.cyut.edu.tw/~ckhung/b/al/asympt.php
排版有點不親民不過也只有這個毛病了

這是個表示時間複雜度的數學計號，而且他表達的是[這傢伙很靠近原函數]

其他會令人混淆的傢伙在這裡 http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations

以下的表格改自wiki

Notation	Name	Intuition	As $n \to \infty$ , eventually...	Definition
$f(n) \in O(g(n))$	Big Omicron; Big O; Big Oh	f 不會比他的Big-O值還大是 f 的upper bond	$\|f(n)\| \leq g(n)\cdot k$ for some k	$\exists k>0, n_0 \; \forall n>n_0 \; \|f(n)\| \leq \|g(n)\cdot k\|$ or $\exists k>0, n_0 \; \forall n>n_0 \; f(n) \leq g(n)\cdot k$
$f(n) \in \Omega(g(n))$ (Note that, since the beginning of the 20th century, papers in number theory have been increasingly and widely using this notation in the weaker sense that f = o(g) is false)	Big Omega	f 不會比他的大Omega值還小是 f 的lower bond	$\|f(n)\| \geq g(n)\cdot k$ for some k	$\exists k>0, n_0 \; \forall n>n_0 \; g(n)\cdot k \leq \|f(n)\|$
$f(n) \in \Theta(g(n))$	Big Theta	如果可以找到一個值既是 f 的Big-O值又是他的Big-Omega值那這個值也是 f 的Big-Theta值	$\|g(n)\|\cdot k_1 \leq \|f(n)\| \leq \|g(n)\|\cdot k_2$ for some k₁, k₂	$\exists k_1,k_2>0, n_0 \; \forall n>n_0$ $\|g(n)\| \cdot k_1 \leq \|f(n)\| \leq \|g(n)\| \cdot k_2$
$f(n) \in o(g(n))$	Small Omicron; Small O; Small Oh	$f$ 比little-o值小而且比Big-O更靠近是 f 的黏巴達upper bond	$\|f(n)\| \le \|g(n)\|\cdot \varepsilon$ for every $\varepsilon$	$\forall \varepsilon>0 \; \exists n_0 \; \forall n>n_0 \; \|f(n)\| \le \|g(n)\cdot \varepsilon\|$
$f(n) \in \omega(g(n))$	Small Omega	$f$ 比little-omega值大而且比Big-omega更靠近是 f 的黏巴達lower bond	$\|f(n)\| \ge \|g(n)\|\cdot k$ for every k	$\forall k>0 \; \exists n_0 \; \forall n>n_0 \; \|g(n)\cdot k\| \le \|f(n)\|$