《数据结构》学习笔记

大家好，欢迎来到IT知识分享网。

1.算法分析的两个主要任务：正确性（不变性 + 单调性） + 复杂度。

2.复杂度分析的主要方法：

• 迭代：级数求和；
• 递归：递归跟踪 + 递推方程
• 猜测 + 验证

3.级数：

• 调和级数：

$$\begin{array}{rl}& h(n)=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}=\Theta (\log n)\end{array}$$

• 对数级数：

$$\log 1+\log 2+\log 3+\cdots +\log n=\log (n!)=\Theta (n\log n)$$

4.一些循环的复杂度估计：

（1）循环体如下：

for (int i = 1; i < n; i <<= 1) for (int j = 0; j < i; j++) O1_Operation(i, j); 

循环体如下：

for (int i = 0; i <= n; i++) for (int j = 1; j < i; j += j) O1_Operation(i, j); 

• 不变性：经 $k$ 轮扫描交换后，最大的 $k$ 个元素必然就位；
• 单调性：经 $k$ 轮扫描交换后，问题规模缩减至 $n-k$；
• 正确性：经至多 $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)$ 蛮力算法：

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)$ 递增策略：

// 考查所有起点相同的区间，它们的总和之间具有相关性 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)$ 分治策略：

// 将整个区间递归地分为三部分：前缀、后缀、跨越切分线的中间部分 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)$ 减治策略：

// 该策略基于这样一个结论： // 记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; }