试图计算算法的时间复杂度

Question

所以昨晚我解决了this LeetCode question。我的解决方案不是很好，相当慢。因此，我试图计算我的算法的复杂性，以与LeetCode在解决方案部分列出的标准算法进行比较。以下是我的解决方案：

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # Get lengths of all strings in the list and get the minimum
        # since common prefix can't be longer than the shortest string.
        # Catch ValueError if list is empty
        try:
            min_len = min(len(i) for i in strs)
        except ValueError:
            return ''

        # split strings into sets character-wise
        foo = [set(list(zip(*strs))[k]) for k in range(min_len)]

        # Now go through the resulting list and check whether resulting sets have length of 1
        # If true then add those characters to the prefix list. Break as soon as encounter
        # a set of length > 1.
        prefix = []
        for i in foo:
            if len(i) == 1:
                x, = i
                prefix.append(x)
            else:
                break
        common_prefix = ''.join(prefix)
        return common_prefix

我在计算复杂性方面有点挣扎。第一步-获取字符串的最小长度-需要O（n），其中n是列表中字符串的数量。那么最后一步也很简单——应该是O（m），其中m是最短字符串的长度

但中间一点令人困惑set(list(zip(*strs)))应该希望再取一次O（m），然后我们再取n次O（mn）。但是总体复杂度是O（mn+m+n），这对于解决方案的速度来说似乎太低了

另一个选择是中间的步骤是O（m^2*n），这更有意义。这里计算复杂性的正确方法是什么

Answer 1

是的，中间部分是O{mn}，整体也是O{mn}，因为这使O{m}和O{n}项的m和n大值相形见绌

您的解决方案具有理想的运行时复杂性顺序

优化：短路

然而，您可能会对其他人有更快的解决方案感到失望。我怀疑其他人可能对第一个不匹配的索引短路

让我们考虑一个26个字符串的测试用例（^ {< CD7>}）。您的解决方案将继续创建一个500长的列表，每个条目包含一组26个元素。同时，如果您短路，您将只处理第一个索引，即一组26个字符

尝试将list更改为generator。这可能就是短路所需的全部

foo = (set(x) for x in zip(*strs)))

您可以跳过min_len检查，因为zip的默认行为是只迭代最短的输入

优化：生成中间结果

我看到您将每个字母附加到一个列表中，然后''.join(lst)。这是有效的，尤其是与迭代附加到字符串的替代方法相比

但是，我们可以同样轻松地保存一个计数器match_len。然后，当我们检测到第一次错误匹配时，只需：

return strs[0][:match_len]