Действительно ли эта временная сложность 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, но это ничего не имеет в строках.

Ответы

Ответ 1

В CPython, стандартной реализации Python, есть деталь реализации, которая делает это обычно O (n), реализованным в коде, который цикл оценки байт-кода вызывает для + или += с двумя строковыми операндами. Если Python обнаруживает, что левый аргумент не имеет других ссылок, он вызывает realloc, чтобы попытаться избежать копирования, изменив размер строки на месте. Это не то, на что вы должны положиться, потому что это детализация реализации, а потому, что если realloc заканчивается необходимость часто перемещать строку, производительность ухудшается до O (n ^ 2) в любом случае.

Без странной детали реализации алгоритм O (n ^ 2) из-за квадратичной суммы копирования. Такой код имел бы смысл только на языке с изменяемыми строками, например С++, и даже на С++ вы хотели бы использовать +=.

Ответ 2

Автор полагается на оптимизацию, которая существует здесь, но не является явно надежной. 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), но это нормально, потому что он находится вне цикла.

Ответ 3

Я нашел этот фрагмент текста на Python Speed > Используйте лучшие алгоритмы и самые быстрые инструменты:

Конкатенация строк лучше всего выполнять с помощью ''.join(seq), который является O(n) процессом. Напротив, использование операторов '+' или '+=' может привести к процессу O(n^2), потому что для каждого промежуточного шага могут быть созданы новые строки. Интерпретатор CPython 2.4 несколько смягчает эту проблему; однако ''.join(seq) остается лучшей практикой