A complexidade de tempo do acréscimo de string iterativa é realmente O (n ^ 2) ou O (n)?

Estou trabalhando em um problema fora do CTCI.

O terceiro problema do capítulo 1 exige que você pegue uma string como

'Mr John Smith '

e pede que você substitua os espaços intermediários por %20:

'Mr%20John%20Smith'

O autor oferece essa solução em Python, chamando-a de 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

Minha pergunta:

Eu entendo que este é O (n) em termos de digitalização através da string real da esquerda para a direita. Mas as strings em Python não são imutáveis? Se eu tiver uma string e adicionar outra string a ela com o +operador, isso não aloca o espaço necessário, copia sobre o original e, em seguida, copia sobre a string anexada?

Se eu tiver uma coleção de nstrings de comprimento 1, isso leva:

1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2

ou O (n ^ 2) vez , sim? Ou estou enganado em como o Python lida com a adição?

Alternativamente, se você estiver disposto a me ensinar a pescar: como eu faria para descobrir isso sozinho? Não tive sucesso em minhas tentativas de pesquisar uma fonte oficial no Google. Encontrei https://wiki.python.org/moin/TimeComplexity, mas não tem nada sobre strings.

Em CPython, a implementação padrão do Python, há um detalhe de implementação que geralmente torna isso O (n), implementado no código que o loop de avaliação de bytecode chama para +ou +=com dois operandos de string . Se o Python detectar que o argumento esquerdo não tem outras referências, ele chamará reallocpara tentar evitar uma cópia redimensionando a string no local. Isso não é algo em que você deve confiar, porque é um detalhe de implementação e porque se reallocacabar precisando mover a string com frequência, o desempenho cai para O (n ^ 2) de qualquer maneira.

Sem o estranho detalhe de implementação, o algoritmo é O (n ^ 2) devido à quantidade quadrática de cópias envolvida. Um código como esse só faria sentido em uma linguagem com strings mutáveis, como C ++, e até mesmo em C ++ que você gostaria de usar +=.

O autor conta com uma otimização que está aqui, mas não é explicitamente confiável. strA = strB + strCé tipicamente O(n), fazer a função O(n^2). No entanto, é muito fácil ter certeza de que todo o processo é O(n), use uma matriz:

output = []
    # ... loop thing
    output.append('%20')
    # ...
    output.append(char)
# ...
return ''.join(output)

Em suma, a appendoperação é amortizada O(1) (embora você possa torná-la forte O(1)pré-alocando o array para o tamanho certo), criando o loop O(n).

E então o joiné também O(n), mas tudo bem porque está fora do loop.

Encontrei este snippet de texto em Python Speed> Use os melhores algoritmos e ferramentas mais rápidas :

A concatenação de strings é melhor feita com o ''.join(seq)que é um O(n)processo. Em contraste, o uso dos operadores '+'ou '+='pode resultar em um O(n^2)processo porque novas strings podem ser criadas para cada etapa intermediária. O interpretador CPython 2.4 mitiga esse problema um pouco; no entanto, ''.join(seq)continua a ser a melhor prática

Para futuros visitantes: Como é uma questão CTCI, qualquer referência ao pacote de aprendizagem urllib não é necessária aqui, especificamente de acordo com o OP e o livro, esta questão é sobre Arrays e Strings.

Esta é uma solução mais completa, inspirada no pseudo de @ 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'))