算法分析的数学基础复习¶
1. Exponents¶
$$X^AX^B = X^{A+B}$$$$\frac{X^A}{X^B} = X^{A-B}$$$$(X^A)^B = X^{A^B}$$$$X^N + X^N = 2X^N \neq X^{2N}$$$$2^N + 2^N = 2^{N+1}$$2. Logarithms¶
$$X^A = B \Leftrightarrow log_XB = A$$$$log_AB = \frac{log_CB}{log_CA}; C \gt 0$$$$logAB = logA + logB$$3. Series¶
$$\sum_{i=0}^N2^i = 2^{N+1} - 1$$$$\sum_{i=0}^NA^i = \frac{A^{N+1} - 1}{A - 1} \leq \frac{1}{1 - A} ; if\ 0 \lt A \lt 1$$$$\sum_{i=1}^Ni = \frac{N(N+1)}{2} \approx \frac{N^2}{2}$$$$\sum_{i=1}^Ni^2 \approx \frac{N^3}{3}$$$$\sum_{i=1}^Ni^k \approx \frac{N^{k+1}}{|k + 1|}; k \neq -1$$4. Modular¶
A is congruent to B modulo N, if N divides (A - B):
$$A \equiv B(mod\ N)$$5. Growth - I¶
$$\exists c, n_0 \in R^+, N \geq n_0, T(N) \leq cf(N), T(N) = O(f(N))$$$$\exists c, n_0 \in R^+, N \geq n_0, T(N) \geq cg(N), T(N) = \Omega(g(N))$$$$T(N) = \Theta(h(N)) \Leftrightarrow T(N) = O(h(N)), T(N) = \Omega(h(N))$$$$T(N) = o(p(N)) \Leftrightarrow T(N) = O(p(N)), T(N) \neq \Omega(p(N))$$e.g.¶
$$ N^2 = O(N^3), N^3 = \Omega(N^2) $$5. Growth - III¶
$$ \lim_{n\rightarrow\infty}f(N)/g(N) = \begin{cases} = 0 \Leftrightarrow f(N) = o(g(N)) \\ \neq 0 \Leftrightarrow f(N) = \Omega(g(N)) \\ = \infty \Leftrightarrow g(N) = o(f(N)) \end{cases} $$L'Hôpital's rule
$$ \lim_{n\rightarrow\infty} f(N)/g(N) = \lim_{n\rightarrow\infty} f'(N)/g'(N),\\if\ \lim_{n\rightarrow\infty} f(N)=\infty, \lim_{n\rightarrow\infty} g(N) = \infty $$2016-03-17