最长公共前缀 - 分而治之方法复杂性分析

Question

我试图了解 D&C 从字符串数组中查找最长公共前缀的方法的时间和 space 复杂度是如何得出的。示例：字符串数组为 ["leet"、"leetcode"、"leeds"、"le"]，输出为 "le" 这是一个 leetcode 问题 14

代码：

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";    
        return longestCommonPrefix(strs, 0 , strs.length - 1);
}

private String longestCommonPrefix(String[] strs, int l, int r) {
    if (l == r) {
        return strs[l];
    }
    else {
        int mid = (l + r)/2;
        String lcpLeft =   longestCommonPrefix(strs, l , mid);
        String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
        return commonPrefix(lcpLeft, lcpRight);
   }
}

String commonPrefix(String left,String right) {
    int min = Math.min(left.length(), right.length());       
    for (int i = 0; i < min; i++) {
        if ( left.charAt(i) != right.charAt(i) )
            return left.substring(0, i);
    }
    return left.substring(0, min);
}

他们网站上所述的复杂性分析 时间复杂度：O(S)，其中S为数组中所有字符的个数，S = mn。时间复杂度为 T(n) = 2 T(n/2) + O(m)。因此时间复杂度为 O(S)。 Space Complexity:O(mlog(n))

我理解了 T(n) = 2 T(n/2) + O(m) 的部分，但是他们是如何从那里导出 m*n 作为时间复杂度的。对于 space 复杂性，我认为我们正在考虑递归树的高度乘以每次递归调用所花费的成本。

n为数组中字符串的个数，m为前缀长度

Answer 1

m*n 复杂性来自 O(m) 项。它被复制（执行）n 次：在每次迭代中，您将列表分成两半（按字符串的数量，n），向下挖掘直到您的基本案例为每个 n 字符串。每个都执行 O(m) 操作。

此外，每个 merge 执行一个 O(m) 操作，总共 2*n-1 个操作。 2*n-1 是 O(n)。 O(m) * O(n) 是 O(mn).

够清楚了吧？

最长公共前缀 - 分而治之方法复杂性分析

Longest Common Prefix - Divide and Conquer approach complexity analysis

algorithm

time-complexity

divide-and-conquer

space-complexity