Действительно ли эта временная сложность O (n ^ 2)?
Я работаю над проблемой из CTCI.
В третьей проблеме главы 1 вы берете строку, такую как
'Mr John Smith '
и попросит заменить промежуточные пространства %20 :
'Mr%20John%20Smith'
Автор предлагает это решение в Python, называя его O (n):
def urlify(string, length): '''function replaces single spaces with %20 and removes trailing spaces''' counter = 0 output = '' for char in string: counter += 1 if counter > length: return output elif char == ' ': output = output + '%20' elif char != ' ': output = output + char return output
Мой вопрос:
Я понимаю, что это O (n) в терминах сканирования через фактическую строку слева направо. Но не являются ли строки в Python неизменяемыми? Если у меня есть строка, и я добавляю к ней еще одну строку с оператором + , не выделяет ли она необходимое пространство, копирует поверх оригинала, а затем копирует строку добавления?
Если у меня есть набор из n строк, каждый из которых имеет длину 1, то это берет:
1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2
или O (n ^ 2), да? Или я ошибаюсь в том, как Python обрабатывает приложение?
В качестве альтернативы, если вы захотите научить меня, как ловить рыбу: как мне это узнать для себя? Я не увенчался успехом в попытках Google использовать официальный источник. Я нашел https://wiki.python.org/moin/TimeComplexity, но это ничего не имеет в строках.
3 Solutions collect form web for “Действительно ли эта временная сложность O (n ^ 2)?”
В CPython, стандартной реализации Python, есть деталь реализации, которая делает это, как правило, O (n), реализованным в коде, цикл обработки байтовых кодов вызывает + или += с двумя строковыми операндами . Если Python обнаруживает, что левый аргумент не имеет других ссылок, он вызывает realloc чтобы попытаться избежать копирования, изменив размер строки на месте. Это не то, на что вы должны полагаться, потому что это детализация реализации, и потому что, если realloc конечном итоге нуждается в перемещении строки часто, производительность ухудшается до O (n ^ 2) в любом случае.
Без странной детали реализации алгоритм O (n ^ 2) из-за квадратичной суммы копирования. Подобный код будет иметь смысл только на языке с изменяемыми строками, например C ++, и даже на C ++ вы хотите использовать += .
Автор полагается на оптимизацию, которая происходит здесь, но не является явно надежной. strA = strB + strC как правило, O(n) , что делает функцию O(n^2) . Тем не менее, довольно легко убедиться, что весь процесс O(n) , используйте массив:
output = [] # ... loop thing output.append('%20') # ... output.append(char) # ... return ''.join(output)
Вкратце, операция append амортизируется O(1) , (хотя вы можете сделать ее сильной O(1) путем предварительного выделения массива в нужный размер), делая цикл O(n) .
И тогда join также O(n) , но это нормально, потому что оно находится вне цикла.
Я нашел этот фрагмент текста на Python Speed> Используйте лучшие алгоритмы и самые быстрые инструменты :
Конкатенацию строк лучше всего выполнять с помощью
''.join(seq)который является процессомO(n). Напротив, использование операторов'+'или'+='может привести к процессуO(n^2)потому что для каждого промежуточного шага могут быть созданы новые строки. Интерпретатор CPython 2.4 несколько смягчает эту проблему; однако''.join(seq)остается лучшей практикой