CBMS-2016-07

题目来源：[[文字版题库/CBMS/2016#Problem 7|2016#Problem 7]] 日期：2024-07-31 题目主题：CS-算法-递归时间复杂度

Solution

Let’s analyze the time complexity for each recurrence relation separately.

1. $T(n)=T(\lfloor 3n/4\rfloor )+cn$

For this recurrence, we use the Master Theorem. The recurrence is of the form $T(n)=aT(n/b)+f(n)$.

• Here, $a=1$, $b=\frac{4}{3}$, and $f(n)=cn$.
• We need to compare $f(n)$ with $n^{{\log }_{b}a}$.

First, compute ${\log }_{b}a$:

$${\log }_{b}a={\log }_{4/3}1=0$$

According to the Master Theorem:

• If $f(n)=O(n^c)$ where $c<{\log }_{b}a$, then $T(n)=\Theta (n^{{\log }_{b}a})$.
• If $f(n)=\Theta (n^{{\log }_{b}a})$, then $T(n)=\Theta (n^{{\log }_{b}a}\log n)$.
• If $f(n)=\Omega (n^c)$ where $c>{\log }_{b}a$ and $af(n/b)\le kf(n)$ for some $k<1$ and sufficiently large $n$, then $T(n)=\Theta (f(n))$.

In this case, $f(n)=cn=\Theta (n)$ and ${\log }_{b}a=0$.

Since $c>{\log }_{b}a$, we have $T(n)=\Theta (n)$.

Thus, $T(n)\in O(n)$.

2. $T(n)=2T(n-1)+cn$

To solve this recurrence, we can use the iterative method:

$$\begin{array}{rl}T(n)& =2T(n-1)+cn\\ & =2[2T(n-2)+c(n-1)]+cn\\ & =2^{2}T(n-2)+2c(n-1)+cn\\ & =2^2[2T(n-3)+c(n-2)]+2c(n-1)+cn\\ & =2^{3}T(n-3)+2^{2}c(n-2)+2c(n-1)+cn\\ & ⋮\\ & =2^{k}T(n-k)+c\sum _{i=0}^{k-1}{2}^i(n-i)\end{array}$$

When $k=n-1$:

$$\begin{array}{rl}T(n)& =2^{n-1}T(1)+c\sum _{i=0}^{n-2}{2}^i(n-i)\\ & =2^{n-1}c+c\sum _{i=0}^{n-2}{2}^i(n-i)\\ & =2^{n-1}c+c\left(\sum _{i=1}^{n-1}{2}^i(n-i+1)-\sum _{i=0}^{n-2}{2}^i(n-i)\right)\\ & =2^{n-1}c+c\left(2^n+\sum _{i=1}^{n-2}{2}^i(n-i+1)-\sum _{i=1}^{n-2}{2}^i(n-i)-n\right)\\ & =2^{n-1}c+c\left(2^n-n+\sum _{i=1}^{n-2}{2}^i\right)\end{array}$$

The sum ${\sum }_{i=1}^{n-2}{2}^i$ is a geometric series:

$$\sum _{i=1}^{n-2}{2}^i=2^{n-1}-2$$

Thus, $T(n)$ can be approximated by:

$$T(n)=\Theta (2^n)=O(3^n)$$

Thus, $T(n)\in O(3^n)$.

3. $T(n)=T(n-1)+c(n^2+n)$

This is a non-homogeneous linear recurrence relation. We can use the iterative method:

$$\begin{array}{rl}T(n)& =T(n-1)+c(n^2+n)\\ & =T(n-2)+c((n-1{)}^2+(n-1))+c(n^2+n)\\ & =T(n-3)+c((n-2{)}^2+(n-2))+c((n-1{)}^2+(n-1))+c(n^2+n)\\ & ⋮\\ & =T(1)+c\sum _{k=1}^{n-1}(k^2+k)\\ & =c+c\sum _{k=1}^{n-1}(k^2+k)\end{array}$$

The sum ${\sum }_{k=1}^{n-1}{k}^2$ is:

$$\sum _{k=1}^{n-1}{k}^2=\frac{(n-1)n(2n-1)}{6}$$

And the sum ${\sum }_{k=1}^{n-1}k$ is:

$$\sum _{k=1}^{n-1}k=\frac{(n-1)n}{2}$$

Therefore:

$$\begin{array}{rl}T(n)& =c+c\left(\frac{(n-1)n(2n-1)}{6}+\frac{(n-1)n}{2}\right)\\ & =c+c\left(\frac{(n-1)n(2n-1+3)}{6}\right)\\ & =c+c\left(\frac{(n-1)n(2n+2)}{6}\right)\\ & =c+\frac{c(n-1)n(n+1)}{3}\\ & =\Theta (n^3)\end{array}$$

Thus, $T(n)\in O(n^3)$.

4. $T(n)=T(\lfloor n/2\rfloor )+c$

For this recurrence, we again use the Master Theorem. The recurrence is of the form $T(n)=aT(n/b)+f(n)$.

• Here, $a=1$, $b=2$, and $f(n)=c$.
• We need to compare $f(n)$ with $n^{{\log }_{b}a}$.

First, compute ${\log }_{b}a$:

$${\log }_{b}a={\log }_{2}1=0$$

According to the Master Theorem:

• If $f(n)=O(n^c)$ where $c<{\log }_{b}a$, then $T(n)=\Theta (n^{{\log }_{b}a})$.
• If $f(n)=\Theta (n^{{\log }_{b}a})$, then $T(n)=\Theta (n^{{\log }_{b}a}\log n)$.
• If $f(n)=\Omega (n^c)$ where $c>{\log }_{b}a$ and $af(n/b)\le kf(n)$ for some $k<1$ and sufficiently large $n$, then $T(n)=\Theta (f(n))$.

In this case, $f(n)=c=\Theta (1)$ and ${\log }_{b}a=0$.

Since $f(n)$ is $\Theta (n^0)$:

$$T(n)=\Theta (\log n)$$

Thus, $T(n)\in O(\log n)$.

5. $T(n)=2T(\lfloor n/2\rfloor )+cn$

For this recurrence, we use the Master Theorem. The recurrence is of the form $T(n)=aT(n/b)+f(n)$.

• Here, $a=2$, $b=2$, and $f(n)=cn$.
• We need to compare $f(n)$ with $n^{{\log }_{b}a}$.

First, compute ${\log }_{b}a$:

$${\log }_{b}a={\log }_{2}2=1$$

According to the Master Theorem:

• If $f(n)=O(n^c)$ where $c<{\log }_{b}a$, then $T(n)=\Theta (n^{{\log }_{b}a})$.
• If $f(n)=\Theta (n^{{\log }_{b}a})$, then $T(n)=\Theta (n^{{\log }_{b}a}\log n)$.
• If $f(n)=\Omega (n^c)$ where $c>{\log }_{b}a$ and $af(n/b)\le kf(n)$ for some $k<1$ and sufficiently large $n$, then $T(n)=\Theta (f(n)$.

In this case, $f(n)=cn=\Theta (n)$ and ${\log }_{b}a=1$.

Since $f(n)=\Theta (n^{{\log }_{b}a})$, we have:

$$T(n)=\Theta (n\log n)$$

Thus, $T(n)\in O(n\log n)$.

Summary

• Recurrence 1: $T(n)=\Theta (n)$, $T(n)\in O(n)$.
• Recurrence 2: $T(n)=\Theta (2^n)$, $T(n)\in O(2^n)$.
• Recurrence 3: $T(n)=\Theta (n^3)$, $T(n)\in O(n^3)$.
• Recurrence 4: $T(n)=\Theta (\log n)$, $T(n)\in O(\log n)$.
• Recurrence 5: $T(n)=\Theta (n\log n)$, $T(n)\in O(n\log n)$.

知识点

主定理递归复杂度分析

解题技巧和信息

对于递归方程的时间复杂度分析，使用主定理是一个强大的工具。主定理适用于形如 $T(n)=aT(n/b)+f(n)$ 的递归式。需要注意 $a,b,f(n)$ 的取值以及 $f(n)$ 和 $n^{{\log }_{b}a}$ 的比较来判断最终的时间复杂度。对于不能用主定理的递归式，可以使用展开迭代法逐步分析。

重点词汇

• Recurrence Relation 递归关系
• Master Theorem 主定理
• Time Complexity 时间复杂度
• Logarithm 对数
• Big O Notation 大 O 符号

参考资料

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, Chapter 4.