東京大学 新領域創成科学研究科 メディカル情報生命専攻 2024年8月実施 問題7

标签：

• Tokyo-University
• Asymptotic-Upper-and-Lower-Bound-Proofs
• Recurrence-Relation-Complexity
• Divide-and-Conquer

Author

zephyr-zdz

Description

Let $n$ be a positive integer. Let $f(n)$ and $g(n)$ denote functions that represent computation time for solving a problem of size $n$. To provide an asymptotic upper bound on $f(n)$, we define:

$$O(g(n)) = \left\{ f(n) \;\middle|\; \begin{array}{l} \text{There exist positive constants } c_0 \text{ and } n_0 \text{ such that} \\ f(n) \le c_0 g(n) \text{ for all } n \ge n_0 \end{array} \right\}$$

Let $c\ (\ge 1)$ be a constant number. Prove that the following statements are true:

(1) If $f(n) = 2^n + n^2$, then $f(n) \in O(2^n)$.

(2) If $f(n) = n^3 2^n$, then $f(n) \in O(2^{2n})$.

(3) If $f(1) = c$ and $f(n) = 2f(n-1) + cn \ (n > 1)$, then $f(n) \in O(2^{2n})$.

(4) If $f(1) = c$ and $f(n) = 2f(\lfloor n/2 \rfloor) + cn \ (n > 1)$, where $\lfloor x \rfloor$ denotes the largest integer that is equal to or smaller than real number $x$, then $f(n) \in O(n \log n)$.

题目描述

设 $n$ 为正整数，$f(n)$、$g(n)$ 表示求解规模为 $n$ 的问题所需的计算时间。为给出 $f(n)$ 的渐近上界，定义

$$O(g(n)) = \left\{ f(n) \;\middle|\; \begin{array}{l} \text{存在正常数 } c_0, n_0, \text{ 使得} \\ \text{对一切 } n \ge n_0 \text{ 有 } f(n) \le c_0 g(n) \end{array} \right\}$$

设 $c\ (\ge 1)$ 为常数，证明下列命题成立：

1. 若 $f(n) = 2^n + n^2$，则 $f(n) \in O(2^n)$。
2. 若 $f(n) = n^3 2^n$，则 $f(n) \in O(2^{2n})$。
3. 若 $f(1) = c$ 且 $f(n) = 2f(n-1) + cn\ (n > 1)$，则 $f(n) \in O(2^{2n})$。
4. 若 $f(1) = c$ 且 $f(n) = 2f(\lfloor n/2 \rfloor) + cn\ (n > 1)$，其中 $\lfloor x \rfloor$ 表示不超过实数 $x$ 的最大整数，则 $f(n) \in O(n \log n)$。

各小问都要求按定义给出 $c_0$ 与 $n_0$（或等价的推导），而非仅指出量级。

Kai

Overview

All four parts ask for the same thing: exhibit explicit constants $c_0$ and $n_0$ witnessing the definition of $O(\cdot)$ given above, rather than merely naming the growth rate. Parts (1) and (2) reduce to a single polynomial-versus-exponential lemma — $n^2 \le 2^n$ for $n \ge 4$, and $n^3 \le 2^n$ for $n \ge 10$ — each proved by induction, after which the required bound is immediate. Parts (3) and (4) are recurrences. In (3) the argument decreases by one, so the recurrence can be solved exactly; the closed form turns out to be $\Theta(2^n)$, comfortably below the requested $2^{2n}$. In (4) the argument is halved, which is the classic divide-and-conquer recurrence of merge sort; the floor is handled by strong induction combined with the monotonicity of $t\,(1 + \log_2 t)$, which lets $\lfloor n/2 \rfloor$ be relaxed to $n/2$ without breaking the bound. Throughout, recall that $O$ states only an upper bound, so a loose but correct estimate is a complete answer.

四个小问要求的其实是同一件事：按上面给出的 $O(\cdot)$ 定义，明确给出常数 $c_0$ 与 $n_0$，而不是仅仅指出增长量级。(1) 和 (2) 都归结为一个「多项式 vs 指数」的引理——$n \ge 4$ 时 $n^2 \le 2^n$，$n \ge 10$ 时 $n^3 \le 2^n$——各用归纳法证明后，所需上界立即得到。(3) 和 (4) 是递推式：(3) 中自变量每次减 $1$，可直接求出精确闭式解，其量级为 $\Theta(2^n)$，远低于题目要求的 $2^{2n}$；(4) 中自变量每次减半，即归并排序那类分治递推，取整符号用强归纳法配合 $t\,(1 + \log_2 t)$ 的单调性处理，从而可把 $\lfloor n/2 \rfloor$ 放大为 $n/2$ 而不破坏上界。始终要记得 $O$ 只声明上界，因此偏松但正确的估计就是完整答案。

(1)

First we prove the lemma that $n^2 \le 2^n$ for $n \ge 4$, by mathematical induction.

Base case: For $n = 4$ we have $n^2 = 16$ and $2^n = 16$, so $16 \le 16$ holds.

Inductive step: Assume $n^2 \le 2^n$ for some $n \ge 4$. For $n \ge 3$,

$$n^2 - (2n + 1) = (n-1)^2 - 2 \ge 2^2 - 2 = 2 > 0$$

so $2n + 1 < n^2$. Hence

$$(n+1)^2 = n^2 + 2n + 1 < 2n^2 \le 2 \cdot 2^n = 2^{n+1}$$

which establishes the claim for $n+1$. Therefore $n^2 \le 2^n$ for all $n \ge 4$.

By this lemma, for $n \ge 4$,

$$f(n) = 2^n + n^2 \le 2^n + 2^n = 2 \cdot 2^n$$

Taking $c_0 = 2$ and $n_0 = 4$ satisfies the definition, so $f(n) \in O(2^n)$.

先用数学归纳法证明引理：当 $n \ge 4$ 时 $n^2 \le 2^n$。

基例： $n = 4$ 时 $n^2 = 16$、$2^n = 16$，故 $16 \le 16$ 成立。

归纳步： 设某个 $n \ge 4$ 满足 $n^2 \le 2^n$。当 $n \ge 3$ 时

$$n^2 - (2n + 1) = (n-1)^2 - 2 \ge 2^2 - 2 = 2 > 0$$

即 $2n + 1 < n^2$。于是

$$(n+1)^2 = n^2 + 2n + 1 < 2n^2 \le 2 \cdot 2^n = 2^{n+1}$$

对 $n+1$ 也成立。故对一切 $n \ge 4$ 有 $n^2 \le 2^n$。

由该引理，当 $n \ge 4$ 时 $f(n) = 2^n + n^2 \le 2^n + 2^n = 2 \cdot 2^n$。取 $c_0 = 2$、$n_0 = 4$ 即满足定义，故 $f(n) \in O(2^n)$。

(2)

We prove the lemma that $n^3 \le 2^n$ for $n \ge 10$, by mathematical induction.

Base case: For $n = 10$, $n^3 = 1000 \le 1024 = 2^{10}$.

Inductive step: Assume $n^3 \le 2^n$ for some $n \ge 10$. Since $n \ge 10$ implies $1 + \frac{1}{n} \le \frac{11}{10}$,

$$(n+1)^3 = n^3 \left(1 + \frac{1}{n}\right)^3 \le n^3 \left(\frac{11}{10}\right)^3 = 1.331\, n^3 < 2 n^3 \le 2 \cdot 2^n = 2^{n+1}$$

which establishes the claim for $n+1$. Therefore $n^3 \le 2^n$ for all $n \ge 10$.

By this lemma, for $n \ge 10$,

$$f(n) = n^3 2^n \le 2^n \cdot 2^n = 2^{2n}$$

Taking $c_0 = 1$ and $n_0 = 10$ satisfies the definition, so $f(n) \in O(2^{2n})$.

用数学归纳法证明引理：当 $n \ge 10$ 时 $n^3 \le 2^n$。

基例： $n = 10$ 时 $n^3 = 1000 \le 1024 = 2^{10}$。

归纳步： 设某个 $n \ge 10$ 满足 $n^3 \le 2^n$。由 $n \ge 10$ 得 $1 + \frac{1}{n} \le \frac{11}{10}$，故

$$(n+1)^3 = n^3 \left(1 + \frac{1}{n}\right)^3 \le n^3 \left(\frac{11}{10}\right)^3 = 1.331\, n^3 < 2 n^3 \le 2 \cdot 2^n = 2^{n+1}$$

对 $n+1$ 也成立。故对一切 $n \ge 10$ 有 $n^3 \le 2^n$。

由该引理，当 $n \ge 10$ 时 $f(n) = n^3 2^n \le 2^n \cdot 2^n = 2^{2n}$。取 $c_0 = 1$、$n_0 = 10$ 即满足定义，故 $f(n) \in O(2^{2n})$。

(3)

We first solve the recurrence in closed form. The claim is

$$f(n) = c\left(2^{n+1} - n - 2\right) \qquad (n \ge 1)$$

which we prove by mathematical induction.

Base case: For $n = 1$, $c(2^2 - 1 - 2) = c(4 - 3) = c = f(1)$.

Inductive step: Assume $f(n-1) = c(2^n - (n-1) - 2) = c(2^n - n - 1)$ for some $n - 1 \ge 1$. Then

$$\begin{aligned} f(n) &= 2f(n-1) + cn \\ &= 2c\left(2^n - n - 1\right) + cn \\ &= c\left(2^{n+1} - 2n - 2 + n\right) \\ &= c\left(2^{n+1} - n - 2\right) \end{aligned}$$

so the claim holds for $n$.

Since $n + 2 > 0$ for $n \ge 1$,

$$f(n) = c\left(2^{n+1} - n - 2\right) < c \cdot 2^{n+1} = 2c \cdot 2^n \le 2c \cdot 2^{2n}$$

where the last inequality uses $2^n \le 2^{2n}$ for $n \ge 0$. Taking $c_0 = 2c$ and $n_0 = 1$ satisfies the definition, so $f(n) \in O(2^{2n})$.

Note that this $f(n)$ is in fact in $O(2^n)$; the bound $O(2^{2n})$ asked for here is a loose one.

先求递推式的闭式解。断言

$$f(n) = c\left(2^{n+1} - n - 2\right) \qquad (n \ge 1)$$

用数学归纳法证明。

基例： $n = 1$ 时 $c(2^2 - 1 - 2) = c(4 - 3) = c = f(1)$。

归纳步： 设某个 $n - 1 \ge 1$ 满足 $f(n-1) = c(2^n - n - 1)$，则

$$\begin{aligned} f(n) &= 2f(n-1) + cn \\ &= 2c\left(2^n - n - 1\right) + cn \\ &= c\left(2^{n+1} - 2n - 2 + n\right) \\ &= c\left(2^{n+1} - n - 2\right) \end{aligned}$$

对 $n$ 也成立。

由于 $n \ge 1$ 时 $n + 2 > 0$，有

$$f(n) = c\left(2^{n+1} - n - 2\right) < c \cdot 2^{n+1} = 2c \cdot 2^n \le 2c \cdot 2^{2n}$$

最后一个不等号用到 $n \ge 0$ 时 $2^n \le 2^{2n}$。取 $c_0 = 2c$、$n_0 = 1$ 即满足定义，故 $f(n) \in O(2^{2n})$。

注：该 $f(n)$ 实际上属于 $O(2^n)$，本题要求的 $O(2^{2n})$ 是一个较松的上界。

(4)

Throughout, $\log$ denotes the base-$2$ logarithm $\log_2$ (a change of base only alters the value by a constant factor, which does not affect the claim $O(n \log n)$).

Claim: for every $n \ge 1$,

$$f(n) \le c\, n \left(1 + \log_2 n\right)$$

We prove this by strong induction on $n$.

Base case: For $n = 1$, $f(1) = c$ and the right-hand side is $c \cdot 1 \cdot (1 + 0) = c$, so the claim holds.

Inductive step: Let $n \ge 2$ and assume the claim holds for all $k$ with $1 \le k < n$. Put $m = \lfloor n/2 \rfloor$. Since $n \ge 2$ we have $1 \le m \le n/2 < n$, so the induction hypothesis applies to $m$.

Let $h(t) = t(1 + \log_2 t)$. For $t \ge 1$,

$$h'(t) = 1 + \log_2 t + \frac{1}{\ln 2} > 0$$

so $h$ is increasing. From $m \le n/2$ and $n/2 \ge 1$ we get $h(m) \le h(n/2)$. Therefore

$$\begin{aligned} f(n) &= 2f(m) + cn \\ &\le 2c\, h(m) + cn \\ &\le 2c\, h(n/2) + cn \\ &= 2c \cdot \frac{n}{2}\left(1 + \log_2 n - 1\right) + cn \\ &= c\, n \log_2 n + cn \\ &= c\, n \left(1 + \log_2 n\right) \end{aligned}$$

so the claim holds for $n$.

Moreover, for $n \ge 2$ we have $1 \le \log_2 n$, hence

$$f(n) \le c\, n \left(1 + \log_2 n\right) \le c\, n \left(\log_2 n + \log_2 n\right) = 2c\, n \log_2 n$$

Taking $c_0 = 2c$ and $n_0 = 2$ satisfies the definition, so $f(n) \in O(n \log n)$.

以下 $\log$ 均指以 $2$ 为底的对数 $\log_2$（换底只相差常数倍，不影响 $O(n \log n)$ 这一结论）。

断言：对一切 $n \ge 1$，

$$f(n) \le c\, n \left(1 + \log_2 n\right)$$

对 $n$ 作强归纳法。

基例： $n = 1$ 时 $f(1) = c$，右端为 $c \cdot 1 \cdot (1 + 0) = c$，成立。

归纳步： 设 $n \ge 2$，且断言对一切 $1 \le k < n$ 成立。令 $m = \lfloor n/2 \rfloor$。由 $n \ge 2$ 得 $1 \le m \le n/2 < n$，故归纳假设可用于 $m$。

令 $h(t) = t(1 + \log_2 t)$，当 $t \ge 1$ 时

$$h'(t) = 1 + \log_2 t + \frac{1}{\ln 2} > 0$$

故 $h$ 单调递增。由 $m \le n/2$ 且 $n/2 \ge 1$ 得 $h(m) \le h(n/2)$。于是

$$\begin{aligned} f(n) &= 2f(m) + cn \\ &\le 2c\, h(m) + cn \\ &\le 2c\, h(n/2) + cn \\ &= 2c \cdot \frac{n}{2}\left(1 + \log_2 n - 1\right) + cn \\ &= c\, n \log_2 n + cn \\ &= c\, n \left(1 + \log_2 n\right) \end{aligned}$$

对 $n$ 也成立。

又当 $n \ge 2$ 时 $1 \le \log_2 n$，故

$$f(n) \le c\, n \left(1 + \log_2 n\right) \le c\, n \left(\log_2 n + \log_2 n\right) = 2c\, n \log_2 n$$

取 $c_0 = 2c$、$n_0 = 2$ 即满足定义，故 $f(n) \in O(n \log n)$。