Самая длинная вычислительная сложность подстроки

Мне было интересно узнать о моем, очевидно, кодексе для практической практики класса MX для онлайн-теста, а также предоставленного кода ответа.

Соответствующее задание из класса было следующим:

Напишите программу, которая печатает самую длинную подстроку 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 

какой код более эффективен? Оба они примерно одинаковой длины, но у меня две петли. Это делает его не таким оптимизированным? благодаря

  • Есть ли простой способ переопределить метод объекта списка __getitem__?
  • Почему Python «упреждающе» висит, пытаясь вычислить очень большое число?
  • Как быстро переназначить идентификаторы для последовательных номеров
  • Python `if x is not None` или` if not x is None '?
  • Питонический способ повторения функции
  • Как добавить две серии в dataframe Row wise
  • Нарезка строк в str.format
  • Не удалось установить pip: ошибка отказа в разрешении
  • 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) для своих. Да, это связано с наличием вложенного цикла, которого нет в их ответе.

    Python - лучший язык программирования в мире.