卷別

資料結構與演算法

選擇

國立臺灣大學 2025 · 考試 · 第 9 題

(5 points) 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$ .)

標準解析

AI 已複查