数组倒置
问题描述
任给数组 A[0, n), 将其前后颠倒
统一接口: void reverse(int *A, int lo, int hi);
递归版
1
2
3
4
5
6
void reverse(int *A, int lo, int hi) {
if (lo < hi) { // 问题规模的奇偶性不变, 需要两个递归基
swap(A[lo], A[hi]);
reverse(A, lo + 1, hi - 1);
}
}
迭代原始版
1
2
3
4
5
6
7
8
9
void reverse(int *A, int lo, int hi) {
next:
if (lo < hi) {
swap(A[lo], A[hi]);
lo++;
hi--;
goto next;
}
}
迭代精简版
1
2
3
void reverse(int *A, int lo, int hi) {
while (lo < hi) swap(A[lo++], A[hi--]);
}
分而治之
为求解一个大规模的问题, 可以:
-
将其划分为若干 (通常两个) 子问题, 规模大体相当
-
分别求解子问题
-
由子问题的解, 得到原问题的解
数组求和: 二分递归
1
2
3
4
5
6
7
8
9
/**
* 对 A[lo, hi] 内元素求和
* 入口形式为 sum(A, 0, n - 1)
*/
sum(int A[], int lo, int hi) {
if (lo == hi) return A[lo];
int mi = (lo + hi) >> 1; // 等价于 (lo + hi) / 2
return sum(A, lo, mi) + sum(A, mi + 1, hi);
}
递归跟踪分析
\[\begin{aligned} T(n) &= 各层递归实例所需时间之和 \\ &= O(1) * (2^0 + 2^1 + 2^2 + \cdots + 2^{\log n}) \\ &= O(1) * (2^{\log n + 1} - 1) \\ &= O(n) \end{aligned}\]
递推方程
从递推的角度看, 为求解 sum(A, lo, hi), 需
-
递归求解
sum(A, lo, mi)和sum(A, mi + 1, hi)2 * T(n/2) -
进而将子问题的解累加
O(1) -
递归基: sum(A, lo, lo)
O(1) -
递推方程:
\[\begin{cases} T(n) = 2 * T( \frac{n}{2} ) + O(1) \\ T(1) = O(1) \end{cases} => T(n) = (c_1 + c_2)n - c_1 = O(n)\]
本文由
Oscaner
创作, 采用
知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外, 均为本站原创或翻译, 转载前请务必署名
