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

4 76
python string algorithm string-concatenation

4 ответа:

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

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

69

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

32

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

конкатенация строк лучше всего выполняется с ''.join(seq) что это

24

для будущих посетителей: Так как это вопрос CTCI, любая ссылка на обучение urllib пакет здесь не требуется, в частности, в соответствии с OP и книгой, этот вопрос касается массивов и строк.

вот более полное решение, вдохновленное псевдо @njzk2:

text = 'Mr John Smith'#13 
special_str = '%20'
def URLify(text, text_len, special_str):
    url = [] 
    for i in range(text_len): # O(n)
        if text[i] == ' ': # n-s
            url.append(special_str) # append() is O(1)
        else:
            url.append(text[i]) # O(1)

    print(url)
    return ''.join(url) #O(n)


print(URLify(text, 13, '%20'))
0