试图找出我的函数的 运行 时间
Trying to figure out the run time of my function
我有这个 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 循环，所以 运行-time 类似于 O(n^4)。我不确定这是否正确，因为并非每个循环都遍历输入大小。此外，假设 s = t = n（输入大小）。有什么想法吗？
如果您不相信它是 O(n^5)，请尝试单独计算 运行 字符串 s 的循环次数（即外部两个循环）。 s_start == 0时，内循环运行sn + 1次；当s_start == 1时，内循环运行sn次，以此类推，直到s_start = n - 1，为此内循环运行s两次。
总和
(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)。
我有这个 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 循环，所以 运行-time 类似于 O(n^4)。我不确定这是否正确，因为并非每个循环都遍历输入大小。此外，假设 s = t = n（输入大小）。有什么想法吗？
如果您不相信它是 O(n^5)，请尝试单独计算 运行 字符串 s 的循环次数（即外部两个循环）。 s_start == 0时，内循环运行sn + 1次；当s_start == 1时，内循环运行sn次，以此类推，直到s_start = n - 1，为此内循环运行s两次。
总和
(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)。