Apakah kompleksitas waktu dari string iteratif yang ditambahkan sebenarnya adalah O (n ^ 2), atau O (n)?

Saya sedang mengerjakan masalah di luar CTCI.

Masalah ketiga dari bab 1 apakah Anda mengambil string seperti

'Mr John Smith '

dan meminta Anda untuk mengganti ruang perantara dengan %20:

'Mr%20John%20Smith'

Penulis menawarkan solusi ini dengan Python, menyebutnya 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

Pertanyaan saya:

Saya memahami bahwa ini adalah O (n) dalam hal pemindaian melalui string aktual dari kiri ke kanan. Tapi bukankah string dalam Python tidak bisa diubah? Jika saya memiliki string dan saya menambahkan string lain ke dalamnya dengan +operator, bukankah itu mengalokasikan ruang yang diperlukan, salin yang asli, dan kemudian salin string tambahan?

Jika saya memiliki kumpulan nstring masing-masing dengan panjang 1, maka itu membutuhkan:

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

atau O (n ^ 2) waktu , ya? Atau apakah saya salah dalam cara Python menangani penambahan?

Atau, jika Anda bersedia mengajari saya cara memancing: Bagaimana saya akan mencari tahu sendiri? Saya tidak berhasil dalam upaya saya menggunakan sumber resmi Google. Saya menemukan https://wiki.python.org/moin/TimeComplexity tetapi ini tidak memiliki apa pun di string.

Di CPython, implementasi standar Python, ada detail implementasi yang membuat ini biasanya O (n), diimplementasikan dalam kode yang dipanggil oleh loop evaluasi bytecode untuk +atau +=dengan dua operan string . Jika Python mendeteksi bahwa argumen kiri tidak memiliki referensi lain, ia memanggil reallocuntuk mencoba menghindari salinan dengan mengubah ukuran string di tempatnya. Ini bukan sesuatu yang harus Anda andalkan, karena ini adalah detail implementasi dan karena jika reallocakhirnya perlu sering memindahkan string, performa akan menurun ke O (n ^ 2).

Tanpa detail implementasi yang aneh, algoritme adalah O (n ^ 2) karena jumlah kuadrat penyalinan yang terlibat. Kode seperti ini hanya masuk akal dalam bahasa dengan string yang bisa berubah, seperti C ++, dan bahkan dalam C ++ yang ingin Anda gunakan +=.

Penulis mengandalkan pengoptimalan yang kebetulan ada di sini, tetapi tidak dapat diandalkan secara eksplisit. strA = strB + strCbiasanya O(n), membuat fungsinya O(n^2). Namun, cukup mudah untuk memastikan seluruh prosesnya O(n), gunakan array:

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

Singkatnya, appendoperasi diamortisasi O(1) , (meskipun Anda dapat membuatnya kuat O(1)dengan mengalokasikan array sebelumnya ke ukuran yang tepat), membuat loop O(n).

Dan kemudian joinjuga O(n), tapi tidak apa-apa karena berada di luar loop.

Saya menemukan cuplikan teks ini di Python Speed> Gunakan algoritma terbaik dan alat tercepat :

Penggabungan string paling baik dilakukan dengan ''.join(seq)sebuah O(n)proses. Sebaliknya, menggunakan operator '+'or '+='dapat menghasilkan O(n^2)proses karena string baru dapat dibangun untuk setiap langkah perantara. Penerjemah CPython 2.4 sedikit mengurangi masalah ini; namun, ''.join(seq)tetap menjadi praktik terbaik

Untuk pengunjung selanjutnya: Karena ini adalah pertanyaan CTCI, referensi apa pun untuk mempelajari urllib paket tidak diperlukan di sini, khususnya sesuai OP dan buku, pertanyaan ini tentang Array dan String.

Berikut solusi yang lebih lengkap, terinspirasi dari pseudo @ 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'))