algorithm - 如何计算此最长公共(public)前缀算法实现的运行时复杂度？

Question

下面是我的代码:

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(strs.length ===0) return '';
    let prefix = strs[0];
    for(let i=0; i< strs.length; i++) {
        while(strs[i].indexOf(prefix) !=0) {
            prefix = prefix.substring(0, prefix.length -1);
            if(!prefix) return '';
        } 
    }

    return prefix;
};

这里 for 循环运行 O(n) 次，而 while 循环内部检查前缀是否与 for 循环迭代中的元素匹配 - while 循环也是 O(n) 次吗？请提供见解

Answer 1

令n 为strs 中的字符串数，令平均(或最长)字符串长度为m。您的带有行号的算法如下。

1. var longestCommonPrefix = function(strs) {
2.    if(strs.length ===0) return '';
3.    let prefix = strs[0];
4.    for(let i=0; i< strs.length; i++) {
5.        while(strs[i].indexOf(prefix) !=0) {
6.            prefix = prefix.substring(0, prefix.length - 1);
7.            if(!prefix) return '';
8.        } 
9.     }
10.    return prefix;
11. };

我们只需要估计 for 循环(第 4 行)和 while 循环(第 5 行)的执行次数。正如您所注意到的，for 循环执行了 n 次，因为 n = strs.length。但是，您在 while 循环中确实有一个 return 语句，因此执行可能永远不会到达第 10 行。

现在，对于 while 循环。如前所述，此循环执行前缀的大小 (m)，并且在每次迭代中，indexOf 操作在最坏的情况下需要 O(m^2)(见下一个)段落)。因此，作为字符串数量 (n) 函数的算法时间复杂度为 O(nm^2)。

我们还可以将时间复杂度视为 m 的函数，即每个字符串中的字符数。比较两个字符串需要多长时间？ Java 在这种情况下的实现将采用 O(mk)，其中 m 和 k 分别是两个字符串的长度(请参阅此答案this question ) 和 String class code了解详情。