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∑nkd≈∫0nxd+1dx=d+11xd+1
0n=d+11nd+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=log2i)2⌈log2n⌉−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⌈log2i⌉=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.算法正确性的证明：（以起泡排序为例）
- 不变性：经 k k k 轮扫描交换后，最大的 k k k 个元素必然就位；
- 单调性：经 k k k 轮扫描交换后，问题规模缩减至 n − k n-k n−k；
- 正确性：经至多 n n n 趟扫描后，算法必然终止，且能给出正确解答。
6.封底估算（Back-Of-The-Envelope Calculation）：
（1）1 day = 24h x 60min x 60sec
≈
\approx
≈ 25 x 4000 = 10^5 sec
（2）10^9 sec
≈
\approx
≈ 30 year
7.最长公共子序列：
（1）递归版：
unsigned int lcs(const char* A, int n, const char* B, int m)
{
if (n < 1 || m < 1) return 0; // recursion base
else if (A[n - 1] == B[m - 1]) // decrease-and-conquer
return 1 + lcs(A, n - 1, B, m - 1);
else // divide-and-conquer
return max(lcs(A, n, B, m - 1), lcs(A, n - 1, B, m));
}
（2）迭代版：
unsigned int lcs(const char* A, int n, const char* B, int m)
{
if (n < m)
{
swap(A, B);
swap(n, m); // make sure m <= n
}
unsigned int* lcs1 = new unsigned int[m + 1];
unsigned int* lcs2 = new unsigned int[m + 1];
memset(lcs1, 0x00, sizeof(unsigned int) * (m + 1));
lcs2[0] = 0;
for (int i = 0; i < n; swap(lcs1, lcs2), i++)
for (int j = 0; j < m; j++)
lcs2[j + 1] = (A[i] == B[j]) ? 1 + lcs1[j] : max(lcs2[j], lcs1[j + 1]);
unsigned int res = lcs1[m];
delete [] lcs1; delete [] lcs2;
return res;
}
8.总和最大区段：
（1） O ( n 3 ) O(n^3) O(n3) 蛮力算法：
int gs_BF(int A[], int n)
{
int gs = A[0]; // current max
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) // enumerate every segment
{
int s = 0;
for (int k = i; k <= j; k++) s += A[k];
if (gs < s) gs = s;
}
return gs;
}
（2） O ( n 2 ) O(n^2) O(n2) 递增策略：
// 考查所有起点相同的区间，它们的总和之间具有相关性
int gs_IC(int A[], int n)
{
int gs = A[0]; // current max
for (int i = 0; i < n; i++)
{
int s = 0;
for (int j = i; j < n; j++)
{
s += A[j];
if (gs < s) gs = s;
}
}
return gs;
}
（3） O ( n log n ) O(n\log n) O(nlogn) 分治策略：文章来源：https://www.toymoban.com/news/detail-823945.html
// 将整个区间递归地分为三部分：前缀、后缀、跨越切分线的中间部分
int gs_DC(int A[], int lo, int hi) // 注意区间是左闭右开的：[lo, hi)
{
if (hi - lo < 2) return A[lo]; // recursion base
int mi = (lo + hi) >> 1;
// 寻找跨越切分线左半边的gsL
int gsL = A[mi - 1], sL = 0, i = mi;
while (lo < i--)
{
sL += A[i];
if (gsL < sL) gsL = sL;
}
// 寻找跨越切分线右半边的gsR
int gsR = A[mi], sR = 0, j = mi - 1;
while (++j < hi)
{
sR += A[j];
if (gsR < sR) gsR = sR;
}
return max(gsL + gsR, max(gs_DC(A, lo, mi), gs_DC(A, mi, hi)));
}
（4） O ( n ) O(n) O(n) 减治策略：文章来源地址https://www.toymoban.com/news/detail-823945.html
// 该策略基于这样一个结论：
// 记suffix(k) = A[k, hi), 其中k = max{lo<=i<hi | sum[i, hi)<=0}，
// 则GS(lo, hi) = A[i, j)要么是其真后缀(k <= i < j = hi)，要么与之无交(j <= k)
int gs_LS(int A[], int n) // Linear Scan: O(n)
{
int gs = A[0], s = 0, i = n;
while (0 < i--)
{
s += A[i];
if (gs < s) gs = s;
if (s <= 0) s = 0; // 剪除负和后缀
}
return gs;
}
到了这里，关于《数据结构》学习笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
