Самая длинная вычислительная сложность подстроки
Мне было интересно узнать о моем, очевидно, кодексе для практической практики класса MX для онлайн-теста, а также предоставленного кода ответа.
Соответствующее задание из класса было следующим:
- Как скомпилировать скрипт python для двоичного исполняемого файла
- Как сделать url unencode в Python?
- удалить последнюю строку STDOUT в Python
- python: процесс завершен с кодом выхода 1 при использовании PyCharm и PyQt5
- Разбивка командной строки Python (для «scrapy»)
- Как получить доступ к функции в пакете виртуальной среды на PyCharm
Напишите программу, которая печатает самую длинную подстроку s, в которой буквы появляются в алфавитном порядке. Например, если s = 'azcbobobegghakl', тогда ваша программа должна печатать
Самая длинная подстрока в алфавитном порядке: beggh
Наше автоматическое тестирование даст вам значение s
Мой успешный код:
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)) Логика состоит в том, чтобы увеличить начальную строчную букву и протестировать каждую последующую букву для увеличения значения, а затем сохранить срез, если он больше, чем текущий срез, до тех пор, пока тест не завершится с ошибкой, а начальная буква увеличивает его. В этот момент процесс начинается.
Код 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
какой код более эффективен? Оба они примерно одинаковой длины, но у меня две петли. Это делает его не таким оптимизированным? благодаря
2 Solutions collect form web for “Самая длинная вычислительная сложность подстроки”
Как правило, добавление большего числа циклов замедляет работу. Но это просто грубое правило. Вещи, которые не выглядят как циклы, могут в реальной реализации быть петлями и, таким образом, замедлять работу. Например, невинный код, такой как curString += s[i] может быть довольно медленным. Это потому, что, предполагая, что curString является строкой Python, вы не можете просто добавить к ней еще одно письмо; то, что заканчивается Python, заключается в создании новой строки, которая на 1 символ длиннее старой, затем копирует все старые символы в новую строку, а затем добавляет один новый символ, а затем присваивает эту новую строку curString . Ни одна из реализаций не очень эффективна, так как они делают такие вещи (используя диапазон вместо xrange, копируя фрагменты строк и т. Д.). Однако, полагая, что строки относительно короткие, это также маловероятно.
В любом случае, обе реализации, ваша и ваша, могут быть установлены так, чтобы каждая выполняемая ими операция была эффективной. В этом случае он возвращается к циклам, и их реализация действительно быстрее, чем ваша. Чтобы понять, почему, рассмотрим строку типа «wxyabcd». При рассмотрении первых трех символов («w», «x» и «y») оба алгоритма выполняют почти одно и то же. Но подумайте, что будет дальше. В вашем коде вы встретите «a», обратите внимание, что это не в алфавитном порядке, поэтому вы заканчиваете свой внутренний цикл. Ваш внешний цикл будет иметь b = 1, и вы будете рассматривать все строки, начинающиеся с «x». Тем не менее, это никогда не даст вам более длинную строку, которая началась с «w», поэтому это будет потрачено впустую. Тем не менее, вы закончите проверку «x», «xy» и «y» перед тем, как перейти к проверке строк, начинающихся с «a», в то время как код 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
Как вы можете видеть, их код намного меньше работает. Один из способов взглянуть на это – это то, что они «смотрят» на любой заданный символ в строке только один раз, пока вы будете рассматривать несколько символов несколько раз.
Их код ответа более эффективен, потому что он неоднократно повторяется через подпоследовательности. Учитывая подпоследовательность ABCDE , ваш код отдельно обрабатывает BCDE , CDE и DE в последовательных итерациях, хотя они не могут быть самыми длинными.
Таким образом, наихудшим временем выполнения вашего ответа является O (N ^ 2) по сравнению с O (N) для своих. Да, это связано с наличием вложенного цикла, которого нет в их ответе.