指数
X
A
X
B
=
X
A
+
B
X^AX^B=X^{A+B}
XAXB=XA+B
X
A
X
B
=
X
A
−
B
\frac{X^A}{X^B}=X^{A-B}
XBXA=XA−B
(
X
A
)
B
=
X
A
B
(X^A)^B=X^{AB}
(XA)B=XAB
X
N
+
X
N
=
2
X
N
≠
X
2
N
X^N+X^N=2X^N\neq X^{2N}
XN+XN=2XN=X2N
2
N
+
2
N
=
2
N
+
1
2^N+2^N=2^{N+1}
2N+2N=2N+1
定理1.1
log
A
B
=
l
o
g
C
B
l
o
g
C
A
;
C
>
0
\log_AB=\frac{log_CB}{log_CA};\enspace C>0
logAB=logCAlogCB;C>0
定理1.2
对数
l
o
g
A
B
=
l
o
g
A
+
l
o
g
B
logAB=logA+logB
logAB=logA+logB
l
o
g
A
/
B
=
l
o
g
A
−
l
o
g
B
log{A/B}=logA-logB
logA/B=logA−logB
l
o
g
A
B
=
B
l
o
g
A
log{A^B}=BlogA
logAB=BlogA
l
o
g
X
<
X
(
对
所
有
的
X
>
0
成
立
)
logX<X (对所有的X>0成立)
logX<X(对所有的X>0成立)
l
o
g
1
=
0
,
l
o
g
2
=
1
,
l
o
g
1024
=
10
,
l
o
g
1048576
=
20
,
log\enspace 1=0,\enspace log\enspace 2=1,\enspace log\enspace 1024=10,\enspace log\enspace 1048576=20,
log1=0,log2=1,log1024=10,log1048576=20,
级数
最容易记忆的公式是
∑
i
=
0
N
2
i
=
2
N
+
1
−
1
\sum_{i=0}^{N}2^i=2^{N+1}-1
i=0∑N2i=2N+1−1
和
∑
i
=
0
N
A
i
=
A
N
+
1
−
1
A
−
1
\sum_{i=0}^{N}A^i=\frac{A^{N+1}-1}{A-1}
i=0∑NAi=A−1AN+1−1
在第二个公式中，若0<A<1,则
∑
i
=
0
N
A
i
≤
1
1
−
A
\sum_{i=0}^{N}A^i\le\frac{1}{1-A}
i=0∑NAi≤1−A1
当N趋于∞时该和趋向于1/(1-A)，这些公式就是“几何级数”公式。
任何这样的级数都可以通过基本公式计算其值。
∑
i
=
1
N
i
=
N
(
N
+
1
)
2
≈
N
2
2
\sum_{i=1}^{N}i=\frac{N(N+1)}{2}\approx\frac{N^2}{2}
i=1∑Ni=2N(N+1)≈2N2
下面这两个公式相对没有那么常见
∑
i
=
1
N
i
2
=
N
(
N
+
1
)
(
2
N
+
1
)
6
≈
N
3
3
\sum_{i=1}^{N}i^2=\frac{N(N+1)(2N+1)}{6}\approx\frac{N^3}{3}
i=1∑Ni2=6N(N+1)(2N+1)≈3N3
∑
i
=
1
N
i
k
=
N
k
+
1
∣
k
+
1
∣
,
k
≠
−
1
\sum_{i=1}^{N}i^k=\frac{N^{k+1}}{|k+1|} ,\enspace k\neq-1
i=1∑Nik=∣k+1∣Nk+1,k=−1
当k=-1时，第二个公式不成立，此时需要下面这个公式。数HN叫做调和数，其和叫做调和和。下面近似公式中的误差趋向于 γ ≈0.57721566 ，这个值称为欧拉常数（Euler’s constan）。
H
N
=
∑
i
=
1
N
1
i
≈
l
o
g
e
N
H_N=\sum_{i=1}^{N}{\frac{1}{i}}\approx log_eN
HN=i=1∑Ni1≈logeN
以下是一般的代数运算
∑
i
=
1
N
f
(
N
)
=
N
f
(
N
)
\sum_{i=1}^{N}f(N)=Nf(N)
i=1∑Nf(N)=Nf(N)
∑
i
=
n
0
N
f
(
i
)
=
∑
i
=
1
N
f
(
i
)
−
∑
i
=
1
n
0
−
1
f
(
i
)
\sum_{i=n_0}^{N}f(i)=\sum_{i=1}^{N}f(i)-\sum_{i=1}^{n_0-1}f(i)
i=n0∑Nf(i)=i=1∑Nf(i)−i=1∑n0−1f(i)
模运算
“模”是“Mod”的音译，Mod的含义为求余。
若N整除A-B,那么我们就说A与B模N同余（congruent），记为A≡B(mod N)。
具有以下主要性质
1、自反性：a≡a（mod m）。
2、对称性：若a≡b（mod m）,则b≡a（mod m）。
3、传递性： 若a≡b（mod m)，b≡c（mod m）, 则a≡c（mod m）。
证明方法
证明数据结构分析中的结论的两个最常用的方法是归纳法和反证法。证明一个定理不成立的最好的方法是举出一个反例。
归纳法证明
由归纳法进行的证明有两个标准的部分。第一步是证明基准情形（base case），就是确定定理对于某个（某些）小的（通常是退化的）值的正确性；这一步几乎总是很简单。接着，进行归纳假设（inductive hypothesis）。一般来说，这意味着假设定理对直到某个有限数k的所有情况都是成立的，然后使用这个假设证明定理对下一个值（通常是k+1）也是成立的。至此，证明定理得证（在k是有限的情形下）。
反例法证明
返例法证明是通过假设定理不成立，然后证明该假设导致某个已知的性质不成立，从而说明原假设是错误的。
