Recurrences and analysis tools
導入済み
語彙
| English | 意味 |
|---|---|
| algorithm design and analysis | Constructing algorithms and studying their correctness and resource costs. |
| recurrence/rɪˈkʌrəns/ | An equation expressing a quantity, such as running time, using values for smaller inputs. |
| recursion tree | A diagram of recursive calls used to add work across levels of a recurrence. |
English
The tree is the analysis
- Algorithm design and analysis prices a design before writing it. A recurrence states a recursive algorithm's cost in terms of smaller inputs: $T(n) = 2T(n/2) + \Theta(n)$. The recursion tree draws it: level $i$ has $2^i$ nodes of $n/2^i$, every level costs $\Theta(n)$, the depth is $\log_2 n$ — so $T(n) = \Theta(n \log n)$.
{exercise:uni-cs1001-tree}
実践
For T(n) = 2T(n/2) + n, one tree level costs —
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
Level i has 2^i nodes of n/2^i: the product is n at every level.
English
The master method, one line each
- For $T(n) = aT(n/b) + f(n)$, compare $f(n)$ with $n^{\log_b a}$ (the leaf total). Leaves dominate: $\Theta(n^{\log_b a})$. Balanced: $\Theta(f(n)\log n)$. Root dominates: $\Theta(f(n))$.
- Course cases: $2T(n/2) + n \to n\log n$; $T(n/2) + 1 \to \log n$; $4T(n/2) + n \to n^2$ (leaves $n^{\log_2 4}$ dominate).
{exercise:uni-cs1001-master}
実践
T(n) = 4T(n/2) + n solves to —
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
Leaves dominate: n^(log_2 4) = n^2.
English
Prove it by substitution
- Guess $T(n) \le c\,n\log n$ for $2T(n/2) + n$: substitute and the induction closes whenever $c \ge 1$ — the guess becomes a proof.
- Then measure: merge sort on the fixed 64-element course array makes $310$ comparisons, under the worst-case ceiling $n\log_2 n - n + 1 = 321$. Theory bounds, measurement confirms.
{exercise:uni-cs1001-substitute}
実践
Merge sort on the 64-element course array makes — comparisons
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
Measured 310, under the worst-case ceiling 321 = 64x6 - 64 + 1.