尝试计算算法时间复杂度

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} 项相形见绌 [=16] =] 和 n.

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

优化：短路

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

让我们考虑一个包含 26 个字符串 (['a'*500, 'b'*500, 'c'*500, ...]) 的测试用例。您的解决方案将继续创建一个 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]

尝试计算算法时间复杂度

Trying to calculate algorithm time complexity

python

algorithm

time-complexity

优化：短路

优化：生成中间结果