Divide and conquer
Split a problem into smaller copies of itself, solve them recursively and combine the results: fast exponentiation, maximum subarray, counting inversions, the master theorem, and parallelism.
| Algorithm | Divide | Conquer | Combine |
|---|---|---|---|
Fast exponentiation
Console.WriteLine(Power(3, 13));Console.WriteLine(Power(2, 62));Console.WriteLine(ModPow(7, 1_000_000_000, 1_000_000_007)); static long Power(long x, int n){ if (n == 0) return 1; long half = Power(x, n / 2); // one problem of half the size return n % 2 == 0 ? half * half : half * half * x; // combine} static long ModPow(long x, long n, long mod) // the same idea, as a loop{ long result = 1; x %= mod; while (n > 0) { if ((n & 1) == 1) result = result * x % mod; // this bit of n is set x = x * x % mod; n >>= 1; } return result;}1594323 4611686018427387904 312556845
BigInteger.ModPow.
How fast is a divide-and-conquer algorithm?
| Case | Meaning | Result | Example |
|---|---|---|---|
Maximum subarray
int[] profit = { 3, -8, 5, -1, 6, -9, 4, 2, -3 };Console.WriteLine(MaxSub(profit, 0, profit.Length - 1)); static int MaxSub(int[] a, int lo, int hi){ if (lo == hi) return a[lo]; // one day: nothing to split int mid = lo + (hi - lo) / 2; int left = MaxSub(a, lo, mid); int right = MaxSub(a, mid + 1, hi); int sum = 0, bestLeft = int.MinValue; // best run ending at mid for (int i = mid; i >= lo; i--) { sum += a[i]; bestLeft = Math.Max(bestLeft, sum); } sum = 0; int bestRight = int.MinValue; // best run starting at mid + 1 for (int i = mid + 1; i <= hi; i++) { sum += a[i]; bestRight = Math.Max(bestRight, sum); } return Math.Max(Math.Max(left, right), bestLeft + bestRight);}10
Divide and conquer runs in parallel
Parallel.Invoke runs two halves at once; below a size threshold, do the work sequentially, because starting a task costs more than adding a few thousand numbers.
int[] data = Enumerable.Range(1, 1_000_000).ToArray();Console.WriteLine(Sum(data, 0, data.Length)); static long Sum(int[] a, int lo, int hi) // sums a[lo..hi){ if (hi - lo <= 50_000) // small: just loop { long s = 0; for (int i = lo; i < hi; i++) s += a[i]; return s; } int mid = lo + (hi - lo) / 2; long left = 0, right = 0; Parallel.Invoke(() => left = Sum(a, lo, mid), () => right = Sum(a, mid, hi)); return left + right;}500000500000
{ 5, 3, 8, 1, 4 } has 6. Do it in O(n log n) by changing merge sort: when an item from the right half is placed before the items still waiting in the left half, each of those forms an inversion with it.
Show a hint
right[j] < left[i], all of left[i..] are bigger than right[j]: add left.Length - i to the count.
Show the solution
Console.WriteLine(CountInversions(new[] { 5, 3, 8, 1, 4 }));Console.WriteLine(CountInversions(new[] { 1, 2, 3, 4 }));Console.WriteLine(CountInversions(new[] { 4, 3, 2, 1 })); static long CountInversions(int[] a){ if (a.Length < 2) return 0; int mid = a.Length / 2; var left = a[..mid]; var right = a[mid..]; long count = CountInversions(left) + CountInversions(right); // both halves are now sorted int i = 0, j = 0, k = 0; while (i < left.Length && j < right.Length) { if (left[i] <= right[j]) a[k++] = left[i++]; else { count += left.Length - i; // right[j] jumps ahead of every remaining left item a[k++] = right[j++]; } } while (i < left.Length) a[k++] = left[i++]; while (j < right.Length) a[k++] = right[j++]; return count;}6 0 6
Remember
Divide into smaller copies, conquer recursively, combine the answers. Costs follow recurrences T(n) = aT(n/b) + f(n); the master theorem gives the result. Fewer subproblems beats a faster combine step (Karatsuba: 3 instead of 4). Independent subproblems run naturally in parallel, above a size threshold.