python - 试图找出我的函数的运行时间

Question

我有这段用于查找最长子字符串的 python 代码。我试图找出它的渐近运行时间，我已经找到了答案，但我不确定它是否正确。这是代码:

def longest_substring(s, t):
    best = ' '
    for s_start in range(0, len(s)):
        for s_end in range(s_start, len(s)+1):
            for t_start in range(0, len(t)):
                for t_end in range(t_start, len(t)+1):
                    if s[s_start:s_end] == t[t_start:t_end]:
                        current = s[s_start:s_end]
                            if len(current) > len(best):
                                best = current
    return best

显然这个函数的运行时间很慢。它就是这样设计的。我的方法是，因为有一个 for 循环和 3 个更多的嵌套 for 循环，所以运行时类似于 O(n^4)。我不确定这是否正确，因为并非每个循环都遍历输入大小。此外，假设 s = t = n(输入大小)。有什么想法吗？

Answer 1

如果您不相信它是 O(n^5)，请尝试单独计算字符串 s 运行的循环次数(即外部两个循环)。当s_start == 0时，内循环运行n + 1次；当s_start == 1时，内循环运行n次，依此类推，直到s_start = n - 1，为此内循环运行两次。

总和

(n + 1) + (n) + (n - 1) + ... + 2

是等差级数，其公式为

((n + 1) + 2) * n / 2

这是 O(n^2)。

一个额外的 n 因子来自 s[s_start:s_end] == t[t_start:t_end]，也就是 O(n)。