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

Question

我试图了解 D&C 从字符串数组中查找最长公共(public)前缀的方法的时间和空间复杂度是如何得出的。示例:字符串数组是 ["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)。空间复杂度:O(mlog(n))

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

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

Answer 1

m*n 复杂度来自 O(m) 项。它被复制(执行)n 次:在每次迭代中，您将列表分成两半(按字符串的数量，n)，向下挖掘直到您的基本情况被执行一次对于每个 n 字符串。其中每一个都执行一个O(m) 操作。

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

够清楚了吗？