递推方程

递推（Recurrence）

递归算法无法直接根据语句的执行次数计算出时间复杂度，但是可以通过递推方程迭代展开进行求解。

求和

int sum(int n) {
    if (n <= 0) {
        return 0;
    }
    return sum(n - 1) + n;
}

T(n) = \begin{cases} 1 & n = 0 \\ T(n-1) + 1 & n \ge 1 \end{cases}

\begin{aligned} T(n) &= T(n-1) + 1 \\ &= [T(n-2) + 1] + 1 \\ &= [[T(n-3) + 1] + 1] + 1 \\ &= \dots \\ &= T(n-k) + k \\ \\ n-k &= 0 \Rightarrow n=k \\ \\ T(n) &= T(n-n) + n \\ &= T(0) + n \\ &= 1+n \\ &= O(n) \end{aligned}

题目

递归求和满足 T(n) = T(n-1) + 1 且 T(0) = 1。展开到基本情况需要多少层？

插入排序

void insertion_sort(int arr[], int n) {
    if (n <= 1) {
        return;
    }
    insertion_sort(arr, n - 1);
    int last = arr[n - 1];
    int j = n - 2;
    while (j >= 0 && arr[j] > last) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = last;
}

T(n) = \begin{cases} 1 & n \le 1 \\ T(n-1) + n & n > 1 \end{cases}

\begin{aligned} T(n) &= T(n-1) + n \\ &= T(n-2) + (n-1) + n \\ &= T(n-3) + (n-2) + (n-1) + n \\ &= \dots \\ &= T(n-k) + \sum_{i=0}^{k-1}(n-i) \\ \\ n-k &= 1 \Rightarrow k=n-1 \\ \\ T(n) &= T(1) + \sum_{i=2}^{n}i \\ &= 1 + \frac{n(n+1)}{2} - 1 \\ &= O(n^2) \end{aligned}

题目

递归插入排序最坏情况下满足 T(n) = T(n-1) + n。展开后新增工作量形成什么序列？

汉诺塔

有三根柱子 A、B、C，A 柱子上从下到上套有 $n$ 个圆盘，要求将 A 柱子上的圆盘移动到 C 柱子上。每次只能移动一个圆盘，且大圆盘始终不能叠在小圆盘上面。

递归算法求解汉诺塔问题：

将前 $n-1$ 个圆盘从 A 柱借助于 C 柱搬到 B 柱。
将最后一个圆盘直接从 A 柱搬到 C 柱。
将 $n-1$ 个圆盘从 B 柱借助于 A 柱搬到 C 柱。

void hanoi(int n, char A, char B, char C) {
    if (n == 1) {
        move(1, A, C);
    } else {
        hanoi(n - 1, A, C, B);
        move(n, A, C);
        hanoi(n - 1, B, A, C);
    }
}

把四个圆盘从 A 柱搬到 C 柱。先点击来源柱，再点击目标柱；最优解需要 15 步。

步数：0 / 最优 15

T(n) = \begin{cases} 1 & n=1 \\ 2T(n-1)+1 & n>1 \end{cases}

\begin{aligned} T(n) &= 2T(n-1)+1 \\ &= 2[2T(n-2)+1]+1 \\ &= 2[2[2T(n-3)+1]+1]+1 \\ &= \dots \\ &= 2^kT(n-k)+2^k-1 \\ \\ n-k &= 1 \Rightarrow n=k+1 \\ \\ T(n) &= 2^{n-1}T(1)+2^{n-1}-1 \\ &= 2^{n-1}+2^{n-1}-1 \\ &= 2^n-1 \\ &= O(2^n) \end{aligned}

题目

汉诺塔递推式 T(n) = 2T(n-1) + 1 中的系数 2 表示什么？

假设每次移动花费 1 秒，解决一个 64 层的汉诺塔问题大约需要 5800 亿年。

对下面三组递推方程使用迭代展开法。每题至少写出前两次展开、一般的第 k 次展开、终止条件和最终渐近复杂度。

T(0) = 1，T(n) = T(n-1) + 3。
T(0) = 1，T(n) = T(n-1) + n。
T(1) = 1，T(n) = 2T(n-1) + 2。

递推方程

递推（Recurrence）

递归算法无法直接根据语句的执行次数计算出时间复杂度，但是可以通过递推方程迭代展开进行求解。

求和

int sum(int n) {
    if (n <= 0) {
        return 0;
    }
    return sum(n - 1) + n;
}

T(n) = \begin{cases} 1 & n = 0 \\ T(n-1) + 1 & n \ge 1 \end{cases}

\begin{aligned} T(n) &= T(n-1) + 1 \\ &= [T(n-2) + 1] + 1 \\ &= [[T(n-3) + 1] + 1] + 1 \\ &= \dots \\ &= T(n-k) + k \\ \\ n-k &= 0 \Rightarrow n=k \\ \\ T(n) &= T(n-n) + n \\ &= T(0) + n \\ &= 1+n \\ &= O(n) \end{aligned}

题目

递归求和满足 T(n) = T(n-1) + 1 且 T(0) = 1。展开到基本情况需要多少层？

插入排序

void insertion_sort(int arr[], int n) {
    if (n <= 1) {
        return;
    }
    insertion_sort(arr, n - 1);
    int last = arr[n - 1];
    int j = n - 2;
    while (j >= 0 && arr[j] > last) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = last;
}

T(n) = \begin{cases} 1 & n \le 1 \\ T(n-1) + n & n > 1 \end{cases}

\begin{aligned} T(n) &= T(n-1) + n \\ &= T(n-2) + (n-1) + n \\ &= T(n-3) + (n-2) + (n-1) + n \\ &= \dots \\ &= T(n-k) + \sum_{i=0}^{k-1}(n-i) \\ \\ n-k &= 1 \Rightarrow k=n-1 \\ \\ T(n) &= T(1) + \sum_{i=2}^{n}i \\ &= 1 + \frac{n(n+1)}{2} - 1 \\ &= O(n^2) \end{aligned}

题目

递归插入排序最坏情况下满足 T(n) = T(n-1) + n。展开后新增工作量形成什么序列？

汉诺塔

递归算法求解汉诺塔问题：

将前 $n-1$ 个圆盘从 A 柱借助于 C 柱搬到 B 柱。
将最后一个圆盘直接从 A 柱搬到 C 柱。
将 $n-1$ 个圆盘从 B 柱借助于 A 柱搬到 C 柱。

void hanoi(int n, char A, char B, char C) {
    if (n == 1) {
        move(1, A, C);
    } else {
        hanoi(n - 1, A, C, B);
        move(n, A, C);
        hanoi(n - 1, B, A, C);
    }
}

把四个圆盘从 A 柱搬到 C 柱。先点击来源柱，再点击目标柱；最优解需要 15 步。

步数：0 / 最优 15

T(n) = \begin{cases} 1 & n=1 \\ 2T(n-1)+1 & n>1 \end{cases}

\begin{aligned} T(n) &= 2T(n-1)+1 \\ &= 2[2T(n-2)+1]+1 \\ &= 2[2[2T(n-3)+1]+1]+1 \\ &= \dots \\ &= 2^kT(n-k)+2^k-1 \\ \\ n-k &= 1 \Rightarrow n=k+1 \\ \\ T(n) &= 2^{n-1}T(1)+2^{n-1}-1 \\ &= 2^{n-1}+2^{n-1}-1 \\ &= 2^n-1 \\ &= O(2^n) \end{aligned}

题目

汉诺塔递推式 T(n) = 2T(n-1) + 1 中的系数 2 表示什么？

假设每次移动花费 1 秒，解决一个 64 层的汉诺塔问题大约需要 5800 亿年。

对下面三组递推方程使用迭代展开法。每题至少写出前两次展开、一般的第 k 次展开、终止条件和最终渐近复杂度。

T(0) = 1，T(n) = T(n-1) + 3。
T(0) = 1，T(n) = T(n-1) + n。
T(1) = 1，T(n) = 2T(n-1) + 2。

递推方程

递推方程

递推（Recurrence）

求和

知识测验

插入排序

知识测验

汉诺塔

挑战四层汉诺塔

知识测验

展开并求解递推方程

递推方程

递推方程

递推（Recurrence）

求和

知识测验

插入排序

知识测验

汉诺塔

挑战四层汉诺塔

知识测验

展开并求解递推方程