Recurrences and analysis tools
Đã giới thiệu
Từ vựng
| English | Ý nghĩa |
|---|---|
| algorithm design and analysis | algorithm design and analysis |
| recurrence/rɪˈkʌrəns/ | recurrence |
| recursion tree | recursion tree |
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}
Luyện tập
For T(n) = 2T(n/2) + n, one tree level costs —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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}
Luyện tập
T(n) = 4T(n/2) + n solves to —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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}
Luyện tập
Merge sort on the 64-element course array makes — comparisons
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Measured 310, under the worst-case ceiling 321 = 64x6 - 64 + 1.