求除斐波那契算法外，分治法避用场景的示例

Hey there! Great question—let's dive into those two anti-pattern scenarios from Neapolitan's Foundation of Algorithms and walk through concrete examples beyond the Fibonacci sequence to see why these divide-and-conquer approaches are best avoided.

Scenario 1: Splitting an n-sized problem into subproblems nearly as large as n #

将规模为n的实例划分为两个或多个规模接近n的实例

Example 1: Naive recursive maximum-finding (bad divide-and-conquer version) #

Suppose we want to find the maximum value in an array of size n. A poorly designed divide-and-conquer approach might split the array into the first element and the remaining n-1 elements, recursively find the max of the n-1 elements, then compare it to the first element.

The recurrence relation here is:
T(n) = T(n-1) + O(1)

This solves to T(n) = O(n)—exactly the same time complexity as a simple linear scan of the array. The only difference? The recursive calls add unnecessary stack overhead, making this divide-and-conquer approach slower than the straightforward method. Since we're not actually breaking the problem into meaningfully smaller subproblems, there's no benefit to using divide-and-conquer here.

Example 2: Mis-split large integer multiplication #

If we're multiplying two n-digit integers, a bad divide-and-conquer strategy might split one number into a 1-digit part and an n-1-digit part, then expand using the distributive property: (a*10^(n-1)+b)*c = a*c*10^(n-1) + b*c. Here, the recursive subproblem of multiplying the n-1-digit number with the n-digit number is nearly as large as the original problem.

The recurrence relation becomes:
T(n) = T(n-1) + O(n)

This solves to T(n) = O(n²)—the same as standard long multiplication. Contrast this with the Karatsuba algorithm, which splits numbers into two n/2-digit subproblems and achieves a better time complexity of O(n^log2(3)) ≈ O(n^1.58). The mis-split version gains nothing from divide-and-conquer and is best avoided.

Scenario 2: Splitting an n-sized problem into nearly n subproblems of size n/c (c is constant) #

将规模为n的实例划分为接近n个规模为n/c的实例（其中c为常数）

Example 1: Bad divide-and-conquer for brute-force string matching #

Say we want to find a pattern of length m (a constant, e.g., m=5) in a text of length n. A flawed divide-and-conquer approach might split the text into n-m+1 subtexts of length m (nearly n subproblems when m is small), compare each subtext to the pattern (O(m) time per comparison), then check if any match exists.

This results in a time complexity of O(n*m)—identical to brute-force string matching—but adds extra overhead from splitting the text into subtexts. Divide-and-conquer doesn't optimize the problem here; it just adds unnecessary steps.

Example 2: Mis-split array sorting #

Suppose we want to sort an array of n elements, but instead of splitting it into two equal halves (like merge sort), we split it into n/2 subarrays of size 2. We sort each 2-element subarray (O(1) time) then merge all these sorted subarrays into one sorted array.

While the final merge step takes O(n log n) time (same as merge sort), generating n/2 subproblems instead of 2 leads to far more recursive calls and overhead. This approach is less efficient than standard merge sort and offers no advantage—another case where divide-and-conquer should be avoided.

内容的提问来源于stack exchange，提问作者Shingolana