数学知识复习
指数
\[X^aX^b = X^{a+b}\] \[\frac{X^a}{X^b} = X^{a-b}\] \[(X^a)^b = X^{ab}\] \[X^n + X^n = 2X^n \neq X^{2n}\] \[2^n + 2^n = 2^{n+1}\] \[e^x = 1 + x + \frac{x^2}{2!} + ... = \sum_{i=0}^\infty \frac{x^i}{i!}\]对所有实数x, 有 \(e^x \geq 1 + x\) ，等于只在 \(x = 0\) 时成立。
当 \(\mid x\mid \leq 1\) 时，我们有近似估计 \(1 + x \leq e^x \leq 1 + x + x^2\) 。
当 \(x \rightarrow 0\) 时，用 \(1 + x\) 作 \(e^x\) 的近似值 \(e^x = 1 + x + \theta(x^2)\) 。
对所有x，有 \(\lim\limits_{n \rightarrow \infty}{(1 + \frac{x}{n})^n} = e^x\) 。
对数
在计算机科学中，除非有特别的声明，所有的对数都是以2为底的。
定义：\(X^A = B\) 当且仅当 \(log_XB = A\)
\[log_AB = \frac{log_CB}{log_CA}; C > 0\] \[logAB = logA + logB\] \[log\frac{A}{B} = logA - logB\] \[log(A^B) = BlogA\] \[logX \lt X (对所有的X \gt 0 成立)\] \[log1 = 0, log2 = 1, log1024 = 10, log1048576 = 20\]级数
\[\sum_{i=0}^N 2^i = 2^{N+1} - 1\] \[\sum_{i=0}^N A^i = \frac{A^{N+1}-1}{A-1}\]如果 \(0 \lt A \lt 1\) 则 \(\sum_{i=0}^N A^i \leq \frac{1}{1-A}\)
渐进分析
定义：如果存在正常数c和\(n_0\)使得当\(N \geq n_0\)时\(T(N) \leq cf(N)\)，则记为\(T(N) = O(f(N))\)。
定义：如果存在正常数c和\(n_0\)使得当\(N \geq n_0\)时\(T(N) \geq cg(N)\)，则记为\(T(N) = \Omega(g(N))\)。
定义：\(T(N) = \Theta(h(N))\)当且仅当\(T(N) = O(h(N))\)且\(T(N) = \Omega(h(N))\)。
定义：如果\(T(N) = O(p(N))\)且\(T(N) \neq \Theta(p(N))\)，则\(T(N) = o(p(N))\)。