1.算法分析的两个主要任务：正确性（不变性 + 单调性） + 复杂度。
2.复杂度分析的主要方法：
3.级数：
（1）算术级数：与末项平方同阶
T
(
n
)
=
1
+
2
+
?
+
n
=
n
(
n
+
1
)
2
=
O
(
n
2
)
T(n) = 1 + 2 + \cdots + n = \frac{n(n+1)}{2} = O(n^2) \notag
T(n)=1+2+?+n=2n(n+1)?=O(n2)
（2）幂方级数：比幂次高出一阶
∑
k
=
0
n
k
d
≈
∫
0
n
x
d
+
1
d
x
=
1
d
+
1
x
d
+
1
∣
0
n
=
1
d
+
1
n
d
+
1
=
O
(
n
d
+
1
)
\sum \limits _{k=0} ^ n k^d \approx \int _0 ^n x^{d+1} \text{d} x = \frac{1}{d+1} x^{d+1} \bigg|_0^n = \frac{1}{d+1} n^{d+1} = O(n^{d+1}) \notag
k=0∑n?kd≈∫0n?xd+1dx=d+11?xd+1
?0n?=d+11?nd+1=O(nd+1)
例如：
T
2
(
n
)
=
1
2
+
2
2
+
?
+
n
2
=
n
(
n
+
1
)
(
2
n
+
1
)
6
=
O
(
n
3
)
T
3
(
n
)
=
1
3
+
2
3
+
?
+
n
3
=
n
2
(
n
+
1
)
2
4
=
O
(
n
4
)
T
4
(
n
)
=
1
4
+
2
4
+
?
+
n
4
=
n
(
n
+
1
)
(
2
n
+
1
)
(
3
n
2
+
3
n
?
1
)
30
=
O
(
n
5
)
\begin{aligned} & T_2(n) = 1^2 + 2 ^ 2 +\cdots + n^2 = \frac{n(n+1)(2n+1)}{6} = O(n^3) \\ & T_3(n) = 1^3 + 2 ^3 +\cdots + n^3 = \frac{n^2(n+1)^2}{4} = O(n^4) \\ & T_4(n) = 1^4 + 2^4 +\cdots + n^4 = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30} = O(n^5) \end{aligned}\notag
?T2?(n)=12+22+?+n2=6n(n+1)(2n+1)?=O(n3)T3?(n)=13+23+?+n3=4n2(n+1)2?=O(n4)T4?(n)=14+24+?+n4=30n(n+1)(2n+1)(3n2+3n?1)?=O(n5)?
（3）几何级数：与末项同阶
T
a
(
n
)
=
a
0
+
a
1
+
?
+
a
n
=
a
n
+
1
?
1
a
?
1
=
O
(
a
n
)
T_a(n) = a^0 + a^1+\cdots+a^n = \frac{a^{n+1}-1}{a-1} = O(a^n) \notag
Ta?(n)=a0+a1+?+an=a?1an+1?1?=O(an)
例如：
1
+
2
+
4
+
?
+
2
n
=
2
n
+
1
?
1
=
O
(
2
n
+
1
)
=
O
(
2
n
)
1+2+4+\cdots+2^n = 2^{n+1}-1=O(2^{n+1})=O(2^n)\notag
1+2+4+?+2n=2n+1?1=O(2n+1)=O(2n)
（4）收敛级数：
1
1
×
2
+
1
2
×
3
+
1
3
×
4
+
?
+
1
(
n
?
1
)
×
n
=
1
?
1
n
=
O
(
1
)
1
+
1
2
2
+
?
+
1
n
2
<
1
+
1
2
2
+
?
+
=
π
2
6
=
O
(
1
)
1
3
+
1
7
+
1
8
+
1
15
+
1
24
+
1
26
+
1
31
+
1
35
+
?
=
1
=
O
(
1
)
\begin{aligned} & \frac{1}{1\times 2} + \frac{1}{2 \times 3} + \frac{1}{3\times4} +\cdots +\frac{1}{(n-1)\times n} = 1-\frac 1 n = O(1) \\ & 1 + \frac{1}{2^2} + \cdots + \frac{1}{n^2} < 1 + \frac{1}{2^2} + \cdots + = \frac{\pi ^2}{6} = O(1) \\ & \frac{1}{3} + \frac{1}{7} + \frac{1}{8} + \frac{1}{15} + \frac{1}{24} + \frac{1}{26} + \frac{1}{31} + \frac{1}{35} + \cdots = 1 = O(1) \end{aligned} \notag
?1×21?+2×31?+3×41?+?+(n?1)×n1?=1?n1?=O(1)1+221?+?+n21?<1+221?+?+=6π2?=O(1)31?+71?+81?+151?+241?+261?+311?+351?+?=1=O(1)?
（5）两个重要级数：
h ( n ) = 1 + 1 2 + 1 3 + ? + 1 n = Θ ( log ? n ) \begin{aligned} & h(n) = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \Theta(\log n) \end{aligned} \notag ?h(n)=1+21?+31?+?+n1?=Θ(logn)?
log ? 1 + log ? 2 + log ? 3 + ? + log ? n = log ? ( n ! ) = Θ ( n log ? n ) \log 1 + \log 2 +\log 3 + \cdots + \log n = \log (n!) = \Theta(n \log n) \notag log1+log2+log3+?+logn=log(n!)=Θ(nlogn)
4.一些循环的复杂度估计：
（1）循环体如下：
for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < i; j++)
O1_Operation(i, j);
其时间复杂度的计算如下：
几何级数：
1
+
2
+
4
+
?
+
2
?
log
?
2
(
n
?
1
)
?
=
∑
k
=
0
?
log
?
2
(
n
?
1
)
?
2
k
(
let?
k
=
log
?
2
i
)
=
2
?
log
?
2
n
?
?
1
=
O
(
n
)
\begin{aligned} \text{几何级数：} \\ & 1 + 2 + 4 + \cdots + 2^{\lfloor \log_2 (n-1) \rfloor} \\ = &\sum \limits _{k=0} ^ {\lfloor \log_2 (n-1) \rfloor} 2^k \quad (\text{let}\ k = \log_2 i) \\ = & 2^{\lceil \log _2 n \rceil} - 1 \\ = & O(n) \end{aligned} \notag
几何级数：===?1+2+4+?+2?log2?(n?1)?k=0∑?log2?(n?1)??2k(let?k=log2?i)2?log2?n??1O(n)?
（2）前置知识：数列
{
n
?
2
n
}
\{n\cdot 2^n\}
{n?2n} 的前
n
n
n 项和：
S
n
=
(
n
?
1
)
?
2
n
+
1
+
2
S_n = (n-1)\cdot 2^{n+1}+2
Sn?=(n?1)?2n+1+2
循环体如下：
for (int i = 0; i <= n; i++)
for (int j = 1; j < i; j += j)
O1_Operation(i, j);
时间复杂度的计算如下：
几何级数：
∑
k
=
0
n
?
log
?
2
i
?
=
O
(
n
log
?
n
)
(
i
=
0
,
1
,
2
,
3
～
4
,
5
～
8
,
9
～
16
,
?
?
)
=
?
0
+
0
+
1
+
2
×
2
+
3
×
2
2
+
4
×
2
4
+
?
=
?
∑
k
=
0
?
log
?
n
(
k
×
2
k
?
1
)
=
?
O
(
log
?
n
×
2
log
?
n
)
\begin{aligned} \text{几何级数：} & \sum \limits _{k=0}^n {\lceil \log _2 i \rceil} = O(n \log n) \\ & (i = 0, 1, 2, 3\sim4, 5\sim 8, 9 \sim 16, \cdots) \\ = &\ 0 + 0 + 1 + 2\times 2 + 3 \times 2^2 + 4 \times 2^4 +\cdots \\ = & \ \sum _{k=0\cdots \log n} (k \times 2^{k-1}) \\ = & \ O(\log n \times 2^{\log n}) \end{aligned} \notag
几何级数：===?k=0∑n??log2?i?=O(nlogn)(i=0,1,2,3～4,5～8,9～16,?)?0+0+1+2×2+3×22+4×24+??k=0?logn∑?(k×2k?1)?O(logn×2logn)?
5.算法正确性的证明：（以起泡排序为例）
6.封底估算（Back-Of-The-Envelope Calculation）：
（1）1 day = 24h x 60min x 60sec
≈
\approx
≈ 25 x 4000 = 10^5 sec