Pertanyaan Apakah kompleksitas waktu ini sebenarnya O (n ^ 2)?


Saya sedang mengerjakan masalah dari CTCI.

Masalah ketiga bab 1 adalah 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 mengerti bahwa ini adalah O (n) dalam hal pemindaian melalui string yang sebenarnya dari kiri ke kanan. Tapi bukankah string Python tidak dapat diubah? Jika saya memiliki string dan saya menambahkan string lain dengannya dengan + operator, bukankah ia mengalokasikan ruang yang diperlukan, menyalin aslinya, dan kemudian menyalin string tambahan?

Jika saya memiliki koleksi n string masing-masing panjang 1, maka itu membutuhkan:

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

atau O (n ^ 2), ya? Atau saya salah dalam bagaimana menangani Python menambahkan?

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


75
2017-11-30 21:06


asal


Jawaban:


Dalam CPython, implementasi standar Python, ada detail implementasi yang membuat ini biasanya O (n), diimplementasikan dalam kode bytecode evaluasi loop panggilan untuk + atau += dengan dua operan string. Jika Python mendeteksi bahwa argumen kiri tidak memiliki referensi lain, ia memanggil realloc untuk mencoba menghindari salinan dengan mengubah ukuran string di tempatnya. Ini bukan sesuatu yang harus Anda andalkan, karena ini merupakan detail implementasi dan karena jika realloc akhirnya perlu sering memindahkan string, kinerja menurun menjadi O (n ^ 2).

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


68
2017-11-30 21:20



Penulis bergantung pada pengoptimalan yang terjadi di sini, tetapi tidak secara eksplisit dapat diandalkan. strA = strB + strC biasanya O(n), membuat fungsinya O(n^2). Namun, sangat mudah untuk memastikan bahwa seluruh prosesnya O(n), gunakan larik:

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

Singkatnya, itu append operasi adalah diamortisasi  O(1), (meskipun Anda bisa membuatnya kuat O(1) dengan pra-mengalokasikan array ke ukuran yang tepat), membuat loop O(n).

Dan kemudian join juga O(n), tapi tidak apa-apa karena itu di luar lingkaran.


32
2017-11-30 21:28



Saya menemukan potongan teks ini Kecepatan Python> Gunakan algoritme terbaik dan alat tercepat:

Penggabungan string paling baik dilakukan dengan ''.join(seq) yang merupakan O(n) proses. Sebaliknya, menggunakan '+' atau '+=' operator dapat menghasilkan O(n^2) proses karena string baru dapat dibangun untuk setiap langkah menengah. Penafsir CPython 2.4 mengurangi masalah ini dengan agak; namun, ''.join(seq) tetap merupakan praktik terbaik


24
2017-11-30 21:26



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

Berikut ini solusi yang lebih lengkap, terinspirasi dari @ njzk2's pseudo:

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
2018-03-26 07:47