最长的子串计算复杂度

编写一个程序，打印其中字母按字母顺序出现的s中最长的子字符串。例如，如果s = 'azcbobobegghakl'，那么你的程序应该打印出来

按照字母顺序排列的最长的子字符串是：beggh

我们的自动化测试将为您提供 s 的价值

成功的代码：

哪个代码更高效？他们两人的长度差不多，但是我有两个圈。这是否使得它不是最优化的？谢谢

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

无论如何，这两个实现都可以被固定，以便每个操作表演很有效率。在这种情况下，它会回到循环，它们的实现确实比你的更快。为了明白为什么，考虑像wxyabcd字符串。当考虑前三个字符（w，x和y）时，两种算法都做了几乎相同的事情。但是要考虑接下来发生的事在你的代码中你会遇到a，注意这不是按字母顺序排列，所以你结束了你的内部循环。你的外部循环将有b = 1，你会考虑所有以x开始的字符串。但是，这些永远不会给你一个更长的字符串，即以w开头的字符串，所以这是浪费精力。在继续检查以a开头的字符串之前，最后检查x，xy和y，而MIT代码将跳转到以a开头的字符串。更具体地说，这里是你的代码将考虑的一组字符串： $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ x xy y a ab abc abcd b bc bcd c cd d

以下是MIT代码将考虑的内容

正如您所看到的，他们的代码的工作量少得多。一种看待它的方法是，他们只查看字符串中任何给定的字符一次，而多次查看一些字符。

I was wondering about my apparently code for an MIT online edx class practice problem vs the provided answer code.

The assignment in question from the class was as follows:

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

My successful code:

The logic is to increment a beginning string letter and test every subsequent letter for increasing value then store the slice if bigger than the current slice, until the test fails and and the beginning letter increments one. At which point the process starts over.

MIT's Code:

which code is more efficient? They both are about the same length, but mine has two loops. Does that make it not as optimized? Thanks

As a rough rule, adding more loops slows things down. But that's just a rough rule. Things that don't look like loops can, in actual implementation, be loops and thus slow things down. For example, innocent looking code like curString += s[i] can actually be quite slow. That's because, assuming curString is a Python string, you can't just add one more letter to it; what Python ends up doing is creating a new string that's 1 character longer than the old one, then copying all the old characters into the new string, then appending the one new character, and then assigning this new string to curString. Neither implementation is terribly efficient as they both do things like this (using range instead of xrange, copying slices of strings, etc.). However, assuming the strings are relatively short this is also unlikely to matter.

In any event, both implementations, your and theirs, could be fixed to so that each operation they perform is efficient. In that case, it does come back to the loops and their implementation is indeed faster than yours. To see why, consider a string like "wxyabcd". When considering the first three characters (the "w", "x", and "y"), both algorithms do pretty much the same thing. But consider what happens next. In your code you'll encounter the "a", note that this isn't in alphabetical order, so you end you inner loop. Your outer loop will have b = 1, and you'll consider the all strings that start with "x". However, these won't ever give you a longer string that the one that started with "w", so this is wasted effort. Still you'll end up checking "x", "xy", and "y" before moving on to check the strings that start with "a", while the MIT code will jump right to the strings that start with "a". To be more concrete, here's the set of strings your code will consider:

And here's what the MIT code will consider

As you can see, their code does a lot less work. One way to look at it is that they "look at" any given character in the string only once while you will look at some characters multiple times.