演算法分析 - 練習題¶

Q1. 遞迴複雜度 - Master Theorem (106)¶

Give asymptotically upper (big O) bounds for $T(n)$ in each of the following recurrences, where we assume that $T(n)$ is constant for small n. Make your bounds as tight as possible and justify your answers.

(a) $T(n) = T(n/3) + 1$

(b) $T(n) = 3T(n/3) + 1$

(d) $T(n) = 2T(\sqrt{n}) + \lg n$

答案與解析

答案:

(a) $T(n) = T(n/3) + 1$ → $O(\log n)$

Master Theorem: $a=1, b=3, f(n)=1$ - $c_{crit} = \log_3 1 = 0$ - $f(n) = 1 = \Theta(n^0)$ - Case 2: $T(n) = \Theta(\log n)$

(b) $T(n) = 3T(n/3) + 1$ → $O(n)$

Master Theorem: $a=3, b=3, f(n)=1$ - $c_{crit} = \log_3 3 = 1$ - $f(n) = 1 = O(n^{1-\epsilon})$ - Case 1: $T(n) = \Theta(n)$

© $T(n) = T(n/10) + T(9n/10) + n$ → $O(n \log n)$

使用 Akra-Bazzi 或遞迴樹： - 每層工作量為 n - 最長路徑：$n \to 9n/10 \to (9/10)^2 n \to ...$ 約 $\log_{10/9} n$ 層 - 總複雜度：$O(n \log n)$

(d) $T(n) = 2T(\sqrt{n}) + \lg n$ → $O(\log n \cdot \log \log n)$

令 $m = \lg n$，$S(m) = T(2^m)$ - $S(m) = 2S(m/2) + m$ - 這是標準形式，解為 $\Theta(m \log m)$ - 代回：$T(n) = \Theta(\log n \cdot \log \log n)$

Q2. 遞迴複雜度分析 (114)¶

Select all the correct statement(s) from the following statements regarding recurrence.

(A) The solution to the recurrence $T(n) = 2T(n/2) + \Theta(n)$ is $\Theta(n^2)$.
(B) The solution to the recurrence $T(n) = 7T(n/2) + \Theta(n^2)$ is $\Theta(n^{\lg 7})$.
(C) The solution to the recurrence $T(n) = \log n + T(\sqrt{n})$ is $\Theta(\log n)$.
(D) The solution to the recurrence $T(n) = 2^n T(n-1)$ is $\Theta((\sqrt{2})^{n^2+n})$. (Assume $T(n) = 1$ for n smaller than some constant c).
(E) The solution to the recurrence $T(n) = T(n/6) + T(7n/9) + O(n)$ is $O(n)$. (Assume $T(n) = 1$ for n smaller than some constant c).

答案與解析

答案: (B)(C)(D)(E)

解析:

(A) 錯誤: $T(n) = 2T(n/2) + \Theta(n)$ - Master Theorem: $a=2, b=2, c_{crit}=1$ - $f(n) = \Theta(n) = \Theta(n^{c_{crit}})$ - Case 2: $T(n) = \Theta(n \log n)$，不是 $\Theta(n^2)$

(B) 正確: $T(n) = 7T(n/2) + \Theta(n^2)$ - $c_{crit} = \log_2 7 \approx 2.807$ - $f(n) = n^2 = O(n^{2.807-\epsilon})$ - Case 1: $T(n) = \Theta(n^{\lg 7})$

(C) 正確: $T(n) = \log n + T(\sqrt{n})$ - 令 $m = \log n$，展開得 $T(n) = \log n + \log \sqrt{n} + ... = \Theta(\log n)$

(D) 正確: $T(n) = 2^n T(n-1)$ - $T(n) = 2^n \cdot 2^{n-1} \cdot ... \cdot 2^1 \cdot T(0) = 2^{n + (n-1) + ... + 1} = 2^{n(n+1)/2}$ - $= (\sqrt{2})^{n(n+1)} = (\sqrt{2})^{n^2+n}$

(E) 正確: 使用 Akra-Bazzi - $1/6^p + (7/9)^p = 1$，解得 $p < 1$ - 因此 $T(n) = O(n)$

Q3. 函數增長比較 (114)¶

Select all pairs of functions in the increasing order of growth. That is, select $g_1, g_2$ if $g_2$ grows faster than $g_1$.

\[f_1(n) = \binom{n}{5}, \quad f_2(n) = 2^{\log^4 n}, \quad f_3(n) = \binom{n}{n-4}, \quad f_4(n) = \sqrt{2^{\sqrt{n}}}, \quad f_5(n) = n^{5(\log n)^2}\]

(A) $f_1(n), f_3(n)$
(B) $f_2(n), f_5(n)$
(C) $f_2(n), f_4(n)$
(D) $f_4(n), f_5(n)$
(E) $f_1(n), f_5(n)$

答案與解析

答案: (B)(C)(E)

解析:

分析各函數： - $f_1(n) = \binom{n}{5} = \Theta(n^5)$ - $f_2(n) = 2^{\log^4 n} = n^{\log^3 n}$（多項式乘以多項式對數次方） - $f_3(n) = \binom{n}{n-4} = \binom{n}{4} = \Theta(n^4)$ - $f_4(n) = \sqrt{2^{\sqrt{n}}} = 2^{\sqrt{n}/2}$（指數型） - $f_5(n) = n^{5(\log n)^2}$（準多項式）

增長順序（慢到快）： $f_3 < f_1 < f_2 < f_5 < f_4$

(A) 錯誤: $f_1 > f_3$
(B) 正確: $f_5 > f_2$
(C) 正確: $f_4 > f_2$
(D) 錯誤: $f_4 > f_5$
(E) 正確: $f_5 > f_1$

Q4. 演算法複雜度分析 (109)¶

Let $f(n)$ be the number of additions in the following algorithm.

for i = 1 to n do
    for j = 1 to i do
        for k = 1 to j do
            C[i][j][k] = A[i][j][k] + B[i][j][k];
        end for
    end for
end for

$f(n)$ is:

| 1. $O(n^2\sqrt{n})$ | 2. $O(n^2 \log n)$ | 3. $O(n^3)$ | 4. $O(n^3 \log n)$ | 5. $O(n^{100})$ |

答案與解析

答案: 3. $O(n^3)$

解析:

計算加法次數： $$f(n) = \sum_{i=1}^{n} \sum_{j=1}^{i} \sum_{k=1}^{j} 1 = \sum_{i=1}^{n} \sum_{j=1}^{i} j$$

\[= \sum_{i=1}^{n} \frac{i(i+1)}{2} = \frac{1}{2} \sum_{i=1}^{n} (i^2 + i)\]

\[= \frac{1}{2} \left( \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} \right)\]

\[= \Theta(n^3)\]

Q5. Amortized Analysis (114)¶

Consider the task of incrementing a k-bit binary counter from all zeroes to all ones. Let A be an array of length k that simulates the counter, where A[0] represents the least significant bit and A[k-1] represents the most significant bit. We implement the INCREMENT() operation as follows:

function INCREMENT()
    i = 0
    while A[i] == 1 do
        A[i] = 0
        i = i + 1
    A[i] = 1

On a deficient RAM machine, writes to certain positions take different amounts of time. Please design a potential function $\Phi(A)$ such that the amortized time per INCREMENT() operation is still $O(1)$.

答案與解析

答案:

Potential Function 設計:

設 $\Phi(A) = c \cdot (\text{A 中 1 的個數})$

其中 c 是一個適當的常數。

分析:

對於一次 INCREMENT 操作： - 假設將 t 個 1 變成 0，然後將 1 個 0 變成 1 - Actual cost = t + 1（假設正常情況） - $\Delta\Phi = c \cdot (1 - t) = c - ct$

Amortized cost = Actual cost + $\Delta\Phi$ = $(t + 1) + (c - ct)$ = $1 + c + t(1 - c)$

若 $c \geq 1$，則 $t(1-c) \leq 0$

Amortized cost $\leq 1 + c = O(1)$

因此 $\Phi(A) = $ A 中 1 的個數，攤銷成本為 $O(1)$

延伸練習¶

更多複雜度分析相關題目： - 107 Data Structure.Pdf Q1-Q7 - 各種複雜度計算 - 114 Data Structure.Pdf Q1 - Randomized Algorithm 分析

Nav

◀ 演算法分析 | 📚 目錄 | 排序 ▶