CBMS-2024B-07

题目来源：Question 07 日期：2024-08-04 题目主题：CS-算法-复杂度分析

解题思路

这道题目主要涉及递归方程的复杂度分析和渐进符号的性质。我们需要运用主定理、迭代法等技巧来解决递归方程，并理解大 O 符号的性质来证明命题。对于最后一个问题，我们需要根据递归方程的形式来判断使用哪种方法求解。

Solution

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

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

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

$=[T(n-2)+2(n-1)]+2n$

$=[T(n-3)+2(n-2)]+2(n-1)+2n$

$=\cdots$

$=T(0)+2[1+2+\cdots +(n-1)+n]$

$=1+2[\frac{n(n+1)}{2}]$

$=1+n(n+1)$

$=n^2+n+1$

Therefore, $T(n)=O(n^2)$.

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

This recurrence fits the form of the Master Theorem with $a=1$, $b=3$, and $f(n)=1$.

Since $f(n)=O(n^{{\log }_{3}1-ϵ})$ for $ϵ>0$, we are in case 1 of the Master Theorem.

Therefore, $T(n)=\Theta (n^{{\log }_{3}1})=\Theta (\log n)$.

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

This recurrence also fits the form of the Master Theorem with $a=2$, $b=2$, and $f(n)=n+1$.

Since $f(n)=\Theta (n^{{\log }_{2}2})=\Theta (n)$, we are in case 2 of the Master Theorem.

Therefore, $T(n)=\Theta (n\log n)$.

4. $T(n)\in O(2^n)$ if and only if $T(n)\in O(e^n)$

This proposition is false. Let’s examine both directions:

Part 1: If $T(n)\in O(2^n)$, then $T(n)\in O(e^n)$

This direction is true.

Proof: Assume $T(n)\in O(2^n)$. By definition, $\exists c>0$ and $n_0>0$ such that $T(n)\le c{2}^n$ for all $n\ge n_0$.

We know that $2^n=(e^{\ln 2}{)}^n=e^{n\ln 2}$.

Since $\ln 2<1$, we have $e^{n\ln 2}<e^n$ for all $n>0$.

Therefore, $T(n)\le c{2}^n=c{e}^{n\ln 2}<c{e}^n$ for all $n\ge n_0$.

This means $T(n)\in O(e^n)$.

Part 2: If $T(n)\in O(e^n)$, then $T(n)\in O(2^n)$

This direction is false.

Consider the function $T(n)=e^n\in O(e^n)$.

${\lim }_{n\to \infty }\frac{e^n}{2^n}={\lim }_{n\to \infty }(\frac{e}{2}{)}^n=\infty$

This means that for any constant $c$, there will always be some $n$ where $e^n>c{2}^n$.

Therefore, the statement “if $T(n)\in O(e^n)$, then $T(n)\in O(2^n)$” is false.

Conclusion

The original proposition is false because while $O(2^n)\subset O(e^n)$, the reverse inclusion does not hold. There are functions in $O(e^n)$ that grow faster than any function in $O(2^n)$.

A correct statement would be: If $T(n)\in O(2^n)$, then $T(n)\in O(e^n)$, but the converse is not necessarily true.

5. $T(n)=aT(\lfloor n/2\rfloor )+\lfloor n{\log }_{2}n\rfloor$

Let’s analyze this recurrence for different cases of $a$. We’ll ignore the floor functions for the asymptotic analysis as they don’t affect the overall complexity.

Case 1: $a<2$

In this case, we can use a variant of the Master Theorem. We have:

$T(n)=aT(n/2)+n\log n$

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

Since $a<2$, we have $n^{{\log }_{2}a}<n$. Therefore, $f(n)=n\log n$ is asymptotically larger.

Thus, $T(n)=\Theta (n\log n)$ when $a<2$.

Case 2: $a=2$

When $a=2$, we have:

$T(n)=2T(n/2)+n\log n$

This case doesn’t fit directly into the Master Theorem. Let’s solve it by substitution:

$T(n)=2T(n/2)+n\log n$ $=2[2T(n/4)+(n/2)\log (n/2)]+n\log n$ $=4T(n/4)+n\log (n/2)+n\log n$ $=4T(n/4)+n\log n+n\log n-n$ $=4T(n/4)+2n\log n-n$

Continuing this process, we get:

$T(n)=nT(1)+n\log n{\sum }_{i=1}^{\log n}2-n{\sum }_{i=1}^{\log n}1$ $=nT(1)+2n{\log }^{2}n-n\log n$

Therefore, when $a=2$, $T(n)=\Theta (n{\log }^{2}n)$.

Case 3: $2<a<4$

In this case, we again compare $n^{{\log }_{2}a}$ with $n\log n$.

Since $2<a<4$, we have $1<{\log }_{2}a<2$.

This means $n<n^{{\log }_{2}a}<n^2$, but $n\log n$ is asymptotically smaller than $n^{{\log }_{2}a}$.

Therefore, when $2<a<4$, $T(n)=\Theta (n^{{\log }_{2}a})$.

Case 4: $a\ge 4$

When $a\ge 4$, we have ${\log }_{2}a\ge 2$.

In this case, $n^{{\log }_{2}a}\ge n^2$, which is asymptotically larger than $n\log n$.

Therefore, when $a\ge 4$, $T(n)=\Theta (n^{{\log }_{2}a})$.

Summary

• For $0<a<2$: $T(n)=\Theta (n\log n)$
• For $a=2$: $T(n)=\Theta (n{\log }^{2}n)$
• For $a\ge 2$: $T(n)=\Theta (n^{{\log }_{2}a})$

知识点

复杂度分析递归主定理

难点思路

第 4 小题的证明和第 5 小题的复杂度分析较为困难。对于第 4 小题，关键是理解指数函数的性质和大 O 符号的定义。对于第 5 小题，由于不能直接应用主定理，需要通过猜测和归纳证明的方法来解决。

解题技巧和信息

1. 对于简单的递归方程，可以尝试使用迭代法直接求解。
2. 对于符合形式的递归方程，优先考虑使用主定理。
3. 当递归方程不能直接应用主定理时，可以尝试猜测复杂度并使用归纳法证明。
4. 在处理渐进符号时，要注意指数函数、对数函数等的性质。

常见算法复杂度排序（从低到高）：

$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)<O(n!)$

重点词汇

• recurrence relation 递归关系
• Master Theorem 主定理
• iteration method 迭代法
• induction proof 归纳证明
• asymptotic notation 渐进符号
• floor function 下取整函数

参考资料

1. Introduction to Algorithms (CLRS), Chapter 4: Divide-and-Conquer
2. Algorithm Design (Kleinberg & Tardos), Chapter 5: Divide and Conquer
3. The Art of Computer Programming (Knuth), Volume 1: Fundamental Algorithms, Section 1.2.11: Asymptotic Representations