python - 最长子串计算复杂度

Question

我想知道我的麻省理工学院在线 edx 类练习题代码与提供的答案代码之间的对比。

类里面的作业如下:

Write a program that prints the longest substring of s in which the letters occur in alphabetical order. For example, if s = 'azcbobobegghakl', then your program should print

Longest substring in alphabetical order is: beggh

Our automating testing will provide a value of s for you

我的成功代码:

curSlice='z'
for b in range(len(s)):
    for e in range(b+1,len(s)):
        if s[e-1]<=s[e]:
            if len(s[b:e+1])>len(aas):
                aas=s[b:e+1]
        else:
            break
print('Longest substring in alphabetical order is: '+str(aas))

逻辑是递增起始字符串字母并测试每个后续字母的递增值，然后存储切片(如果大于当前切片)，直到测试失败并且起始字母递增 1。此时流程重新开始。

MIT 的代码:

curString = s[0]
longest = s[0]
for i in range(1, len(s)):
    if s[i] >= curString[-1]:
        curString += s[i]
        if len(curString) > len(longest):
            longest = curString
    else:
        curString = s[i]
print 'Longest substring in alphabetical order is:', longest

哪个代码效率更高？它们的长度差不多，但我的有两个环。这是否使它没有那么优化？谢谢

Answer 1

作为一个粗略的规则，添加更多循环会减慢速度。但这只是一个粗略的规则。看起来不像循环的东西在实际实现中可能是循环，从而减慢速度。例如，像 curString += s[i] 这样看似无辜的代码实际上可能非常慢。那是因为，假设 curString 是一个 Python 字符串，您不能再向它添加一个字母； Python 最终做的是创建一个比旧字符串长 1 个字符的新字符串，然后将所有旧字符复制到新字符串中，然后附加一个新字符，然后将这个新字符串分配给 curString。这两种实现都不是非常有效，因为它们都做这样的事情(使用范围而不是 xrange，复制字符串切片等)。然而，假设字符串相对较短，这也不太可能重要。

在任何情况下，您的和他们的实现都可以固定，以便它们执行的每个操作都是高效的。在那种情况下，它确实会回到循环，并且它们的实现确实比你的更快。要了解原因，请考虑像“wxyabcd”这样的字符串。在考虑前三个字符(“w”、“x”和“y”)时，两种算法的作用几乎相同。但请考虑接下来会发生什么。在您的代码中，您会遇到“a”，请注意，这不是按字母顺序排列的，因此您结束了内部循环。您的外部循环将有 b = 1，并且您将考虑以“x”开头的所有字符串。然而，这些永远不会给你一个比以“w”开头的字符串更长的字符串，所以这是浪费精力。在继续检查以“a”开头的字符串之前，您仍然会最终检查“x”、“xy”和“y”，而 MIT 代码将直接跳转到以“a”开头的字符串。更具体地说，这是您的代码将考虑的字符串集:

w
wx
wxy
x
xy
y
a
ab
abc
abcd
b
bc
bcd
c
cd
d

这是 MIT 代码将考虑的内容

w
wx
wxy
a
ab
abc
abcd

如您所见，他们的代码所做的工作要少得多。一种看待它的方法是，他们只“查看”字符串中的任何给定字符一次，而您会多次查看某些字符。