最长公共前缀——比较两种算法的时间复杂度

Question

如果比较这两个解决方案，第一个解决方案的时间复杂度是 O(array-len*sortest-string-len)，您可以将其缩短为 O(n*m) 甚至 O(n^2)。第二个似乎 O(n * log n) 因为它有一个排序方法然后比较第一个和最后一个项目所以它是 O(n) 并且对 O 没有任何影响。

但是，比较列表中的字符串项会发生什么。对整数值列表进行排序是 O(n * log n) 但我们不需要比较字符串中的字符才能对它们进行排序吗？那么，如果我说第二个解决方案的时间复杂度是 O(n * log n * longest-string-len)，我错了吗？

此外，由于它在排序时不检查前缀，所以它无论如何都会进行排序（大多数情况下）所以它的最佳情况比其他选项差得多？另外，对于最坏的情况，如果你考虑我提到的那一点，它仍然比第一个解决方案更糟糕？

public string longestCommonPrefix(List<string> input) {
        if(input.Count == 0) return "";
        if(input.Count == 1) return input[0];
        
        var sb = new System.Text.StringBuilder();
        
        for(var charIndex = 0; charIndex < input[0].Length; charIndex++)
        {
            for(var itemIndex = 1; itemIndex < input.Count; itemIndex++)
            {
                if(input[itemIndex].Length > charIndex)
                    return sb.ToString();
                
                if(input[0][charIndex] != input[itemIndex][charIndex])
                    return sb.ToString();
            }
            
            sb.Append(input[0][charIndex]);
        }
        
        return sb.ToString();
    }

static string longestCommonPrefix(String[] a) 
    { 
        int size = a.Length; 
  
        /* if size is 0, return empty string */
        if (size == 0) 
            return ""; 
  
        if (size == 1) 
            return a[0]; 
  
        /* sort the array of strings */
        Array.Sort(a); 
  
        /* find the minimum length from first 
        and last string */
        int end = Math.Min(a[0].Length, 
                            a[size-1].Length); 
  
        /* find the common prefix between the  
        first and last string */
        int i = 0; 
        while (i < end && a[0][i] == a[size-1][i] ) 
            i++; 
  
        string pre = a[0].Substring(0, i); 
        return pre; 
    }

Answer 1

首先，除非我遗漏了一些明显的东西，否则第一种方法在 O(N * shortest-string-length) 中运行；最短，而不是最长。

其次，您不能将 O(n*m) 减少到 O(n^2)：字符串的数量与其长度无关。

最后，你是绝对正确的。排序确实需要 O(n*log(n)*m)，所以在任何情况下它都不会提高性能。

作为旁注，可能事先找到最短的字符串是有益的。这将使 input[itemIndex].Length > charIndex 变得不必要。

最长公共前缀——比较两种算法的时间复杂度

Longest common prefix - comparing time complexity of two algorithms

string

algorithm

big-o

time-complexity

longest-substring