指数公式
- $X^A*X^B=X^{A+B}$
- $X^A/X^B=X^{A-B}$
- $(X^A)^B=X^{AB}$
对数公式
- $X^A=B=>\log_X(B)=A$
- $\log_A(B)=\log_C(B)/\log_C(A),C>0$
- $\log(AB)=\log(A) + \log(B)$
- $\log(A/B)=\log(A) - \log(B)$
- $\log(A^B) = B*\log(A)$
- $X > 0 => \log(X) < X$
级数
- $\sum_{i=0}^{N}A^i=(A^{N+1}-1)/(A-1)$
- $\sum_{i=0}^{N}A^i<=1/(1-A)$当$0<A<1$
- $\sum_{i=1}^{N}i=(N+1)N/2\approx N^2/2$
- $\sum_{i=1}^{N}i^2=(N+1)(2N+1)N/6\approx N^3/3$
- $\sum_{i=1}^{N}i^k\approx N^{k+1}/|K+1|,k\ne -1$
- $H_N =\sum_{i=1}^{N}(1/i)\approx log_e(N),H_N $称为调和数
模运算
- $(A \mod N) = (B \mod N) => N$整除$(A-B)$
- 如果$M>N$，则$M \mod N < M/2$
注：取模运算耗费很大
数据结构证明常用方法
- 归纳法：证明基准情形->归纳假设->证明下一个值也成立
- 反例证明：举出反例
- 反证法：假设定理不成立，然后证明某个已知的性质不成立，从而证明原假设是错误的
递归
当一个函数用自身来定义时就称为递归的，编写递归例程需要遵循四条基本法则：
- 基准情形：必须总有某些基准情形无需递归即可求解
- 不断递进：递归调用总是朝着基准情形推进
- 设计法则：假设所有的递归调用都能运行
- 合成效益法则：求解一个问题同一实例时切勿在不同递归调用中做重复性工作（类似动态规划保存结果）
算法分析基础
- 大$O$标记：如果存在正常数$c$以及$n_0$使得当$N>=n_0$时$T(N)<=cf(N)$，则记为$T(N)=O(f(N))$
- 大$Ω$标记：如果存在正常数$c$以及$n_0$使得当$N>=n_0$时$T(N)>=cf(N)$,则记为$T(N)=Ω(f(N))$
- $Θ$标记：$T(N)=Θ(f(N))$当且仅当$T(N)=O(f(N))$ AND $T(N)=Ω(f(N))$
- 小$o$标记：$T(N)=o(f(N))$当且仅当$T(N)=O(f(N)) AND T(N)!=Ω(f(N))$
- 如果$T_1(N)=O(f(N))$且$T_2(N)=O(g(N))$
则$T_1(N)+T_2(N)=max(O(f(N)),O(g(N))), T_1(N)*T_2(N)=O(f(N)*g(N))$ - 如果$T(N)$是一个$k$次多项式，则$T(N)=Θ(N^k)$
- 对于任意$k,\log^k(N)=O(N)$，表明对数增长十分缓慢
时间复杂度计算一般法则
- FOR循环：一次FOR循环的运行时间至多是该循环语句（包括测试）的运行时间乘以迭代的次数。
- 嵌套的FOR循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句运行时间乘以所有的FOR循环的大小的乘积。
- 顺序语句：将各个语句的运行时间求和即可。
- IF/ELSE语句：IF/ELSE语句运行时间不超过判断再加上两部分运行时间长者的和。
- 如果一个算法用常数时间将问题的的大小削减为其一部分，那么该算法就是$O(\log(N))$；如果使用常数时间只是把问题减少一个常数，那么这种算法就是$O(N)$。
联机算法
在任意时刻算法对要操作的数据只读入（扫描）一次，一旦被读入并处理，它就不需要在被记忆了。而在此处理过程中算法能对它已经读入的数据立即给出相应子序列问题的正确答案。仅需要常量空间并以线性时间运行的联机算法几乎是完美算法。