Divide and conquer
הוצג
מילון מונחים
| English | משמעות |
|---|---|
| merge sort/mɜːdʒ sɔːt/ | Sorting by recursively sorting parts and merging the sorted parts. |
| quicksort | Sorting by partitioning values around a pivot and recursively sorting the partitions. |
English
Split, solve, combine
- Merge sort splits in half, recurses, merges in $\Theta(n)$: $T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n)$. Quicksort moves the work into the partition — the pivot quality decides everything.
{exercise:uni-cs1002-skeleton}
אימונים
Binary search recurrence is —
רמת קושי 1/5 · 100 מטבעות + בונוס קטן בהשלמה הראשונה היום
One recursive call, constant combine: Theta(log n).
English
Quicksort's three worlds
- Balanced pivots: $\Theta(n\log n)$. Sorted input with first-element pivots: $T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$.
- Course measurements on the 64-element array: merge 310 comparisons, quicksort 356, sorted-input worst 2080. Randomised pivots make the expected count $2n\ln n \approx 1.39\,n\log_2 n$.
{exercise:uni-cs1002-quicksort}
אימונים
Sorted input with first-element pivots costs quicksort —
רמת קושי 1/5 · 100 מטבעות + בונוס קטן בהשלמה הראשונה היום
T(n) = T(n-1) + n: each partition peels one element.
English
Two worked patterns
- Maximum subarray by divide and conquer: left best, right best, or the best crossing the middle — the crossing scan is a full pass, so $\Theta(n\log n)$. On $[-2, 1, -3, 4, -1, 2, 1, -5, 4]$ the answer is 6.
- Binary search is the degenerate case: one recursive call, constant combine, $\Theta(\log n)$ — the pattern survives with one branch.
{exercise:uni-cs1002-subarray}
אימונים
The maximum subarray of [-2, 1, -3, 4, -1, 2, 1, -5, 4] sums to —
רמת קושי 1/5 · 100 מטבעות + בונוס קטן בהשלמה הראשונה היום
The run 4, -1, 2, 1 sums to 6.