LeetCode 14：分治法求最长公共前缀的复杂度推导疑问

Hey there! Let's walk through exactly how to calculate the time and space complexity of using a divide-and-conquer approach for the Longest Common Prefix problem (LeetCode 14). I'll reference your example input ["leet", "leetcode", "leeds","le"] to make the reasoning more tangible.

Time Complexity Analysis #

First, let's recap the divide-and-conquer logic for this problem:

1. Split the input string array into two halves recursively until each subarray has just one string.
2. Compute the longest common prefix (LCP) for each half.
3. Merge the results by finding the LCP of the two prefixes from the left and right halves.

Key Assumptions #

Let’s define:

• n: Number of strings in the input array
• m: Maximum length of any string in the array (or the length of the shortest string in the worst case where all strings share a full prefix)

Recursive Relation & Breakdown #

The time complexity follows this recursive formula:
T(n) = 2 * T(n/2) + O(m)

• 2 * T(n/2): We split the array into two halves and solve each half recursively.
• O(m): Merging two LCPs takes up to m character comparisons (since the LCP can’t be longer than the shortest string, which is at most m characters).

Solving the Recurrence #

We can expand the recurrence to see the total cost:

• Level 0 (top level): T(n) = 2*T(n/2) + m
• Level 1: 2*(2*T(n/4) + m) + m = 4*T(n/4) + 2m + m
• Level 2: 8*T(n/8) + 4m + 2m + m
• ...
• After log₂n levels (since we split by 2 each time), we reach T(1) (single string, which takes O(1) time to return as the LCP).

The sum of the merging costs across all levels is m*(2⁰ + 2¹ + ... + 2^(log₂n - 1)). This is a geometric series that sums to m*(n - 1), which simplifies to O(mn).

What About Best/Worst Cases? #

• Worst Case: All strings are identical (e.g., ["aaa", "aaa", "aaa"]). Every merge step compares all m characters, leading to the full O(mn) time.
• Best Case: Strings differ in the first character (e.g., ["apple", "banana", "cherry"]). Merging stops after the first comparison, so the time drops to O(n) (since we only check the first character across all strings).

For your example input, the merge step between "leet" and "le" stops after 2 characters, which is faster than the worst case, but the asymptotic complexity still stays O(mn).

Space Complexity Analysis #

Space complexity comes from two main sources:

1. Recursion Call Stack: The depth of the recursion tree is log₂n (since we split the array in half each time). Each recursive call adds a frame to the stack, so this contributes O(logn) space.
2. Temporary LCP Storage: Each merge step creates a temporary string to store the LCP of two prefixes. The maximum length of this string is m, so this contributes O(m) space. Since we use depth-first recursion, only one temporary LCP string exists at any time (we don’t store all intermediate prefixes simultaneously).

Combining these, the total space complexity is O(m + logn). In most practical cases where m is much larger than logn, this simplifies to O(m).

For your example, the recursion depth is log₂4 = 2, and the largest temporary LCP is "leet" (length 4), so the space used is small.

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