Mengapa kasus terburuk untuk fungsi ini O (n ^ 2)?

Saya mencoba untuk belajar sendiri bagaimana menghitung notasi BigO untuk fungsi arbitrer. Saya menemukan fungsi ini di buku teks. Buku ini menegaskan bahwa fungsinya adalah O (n ² ). Ini memberikan penjelasan mengapa ini terjadi, tetapi saya berjuang untuk mengikuti. Saya bertanya-tanya apakah seseorang mungkin bisa menunjukkan kepada saya matematika di balik mengapa demikian. Pada dasarnya, saya mengerti bahwa itu adalah sesuatu yang kurang dari O (n ³ ), tetapi saya tidak dapat secara mandiri mendarat di O (n ² )

Misalkan kita diberi tiga urutan angka, A, B, dan C. Kita akan mengasumsikan bahwa tidak ada urutan individual yang mengandung nilai duplikat, tetapi mungkin ada beberapa angka yang ada dalam dua atau tiga urutan. Masalah disjointness set tiga-arah adalah untuk menentukan apakah persimpangan dari tiga sekuens kosong, yaitu, bahwa tidak ada elemen x sehingga x ∈ A, x ∈ B, dan x ∈ C.

Kebetulan, ini bukan masalah pekerjaan rumah bagi saya - bahwa kapal telah berlayar bertahun-tahun yang lalu :), hanya saya yang mencoba menjadi lebih pintar.

def disjoint(A, B, C):
        """Return True if there is no element common to all three lists."""  
        for a in A:
            for b in B:
                if a == b: # only check C if we found match from A and B
                   for c in C:
                       if a == c # (and thus a == b == c)
                           return False # we found a common value
        return True # if we reach this, sets are disjoint

[Sunting] Menurut buku teks:

Dalam versi yang ditingkatkan, bukan hanya kita menghemat waktu jika kita beruntung. Kami mengklaim bahwa waktu berjalan kasus terburuk untuk disjoint adalah O (n ² ).

Penjelasan buku ini, yang saya susah payah ikuti, adalah ini:

Untuk menjelaskan keseluruhan waktu berjalan, kami memeriksa waktu yang dihabiskan untuk mengeksekusi setiap baris kode. Manajemen for for over A membutuhkan O (n) waktu. Manajemen for for over B menyumbang total waktu O (n ² ), karena loop tersebut dieksekusi pada n waktu yang berbeda. Tes a == b dievaluasi O (n ² ) kali. Sisa waktu yang dihabiskan tergantung pada berapa banyak pasangan yang cocok (a, b). Seperti yang telah kita catat, paling banyak ada n pasangan demikian, dan demikian pula pengelolaan loop di atas C, dan perintah-perintah di dalam tubuh loop itu, gunakan paling banyak pada waktu O (n ² ). Total waktu yang dihabiskan adalah O (n ² ).

(Dan untuk memberikan kredit yang layak ...) Buku ini adalah: Struktur Data dan Algoritma dalam Python oleh Michael T. Goodrich et. semua, Penerbitan Wiley, hal. 135

[Sunting] Suatu pembenaran; Di bawah ini adalah kode sebelum optimasi:

def disjoint1(A, B, C):
    """Return True if there is no element common to all three lists."""
       for a in A:
           for b in B:
               for c in C:
                   if a == b == c:
                        return False # we found a common value
return True # if we reach this, sets are disjoint

Pada contoh di atas, Anda dapat dengan jelas melihat bahwa ini adalah O (n ³ ), karena setiap loop harus dijalankan sepenuhnya. Buku ini akan menyatakan bahwa dalam contoh sederhana (diberikan pertama), loop ketiga hanya kompleksitas O (n ² ), sehingga persamaan kompleksitas berjalan sebagai k + O (n ² ) + O (n ² ) yang akhirnya menghasilkan O (n ² ).

Meskipun saya tidak dapat membuktikan hal ini (dengan demikian pertanyaannya), pembaca dapat setuju bahwa kompleksitas dari algoritma yang disederhanakan setidaknya kurang dari aslinya.

[Sunting] Dan untuk membuktikan bahwa versi yang disederhanakan adalah kuadratik:

if __name__ == '__main__':
    for c in [100, 200, 300, 400, 500]:
        l1, l2, l3 = get_random(c), get_random(c), get_random(c)
        start = time.time()
        disjoint1(l1, l2, l3)
        print(time.time() - start)
        start = time.time()
        disjoint2(l1, l2, l3)
        print(time.time() - start)

Hasil:

0.02684807777404785
0.00019478797912597656
0.19134306907653809
0.0007600784301757812
0.6405444145202637
0.0018095970153808594
1.4873297214508057
0.003167390823364258
2.953308343887329
0.004908084869384766

Karena perbedaan kedua sama, fungsi yang disederhanakan memang kuadratik:

[Sunting] Dan bukti lebih lanjut:

Jika saya menganggap kasus terburuk (A = B! = C),

if __name__ == '__main__':
    for c in [10, 20, 30, 40, 50]:
        l1, l2, l3 = range(0, c), range(0,c), range(5*c, 6*c)
        its1 = disjoint1(l1, l2, l3)
        its2 = disjoint2(l1, l2, l3)
        print(f"iterations1 = {its1}")
        print(f"iterations2 = {its2}")
        disjoint2(l1, l2, l3)

hasil:

iterations1 = 1000
iterations2 = 100
iterations1 = 8000
iterations2 = 400
iterations1 = 27000
iterations2 = 900
iterations1 = 64000
iterations2 = 1600
iterations1 = 125000
iterations2 = 2500

Menggunakan uji perbedaan kedua, hasil kasus terburuk adalah kuadratik.

Buku itu memang benar, dan itu memberikan argumen yang bagus. Perhatikan bahwa timing bukan merupakan indikator kompleksitas algoritme yang dapat diandalkan. Pengaturan waktu mungkin hanya mempertimbangkan distribusi data khusus, atau kasus uji mungkin terlalu kecil: kompleksitas algoritme hanya menjelaskan bagaimana skala penggunaan sumber daya atau runtime di luar beberapa ukuran input yang sesuai.

Buku ini membuat argumen bahwa kompleksitas adalah O (n²) karena if a == bcabang dimasukkan paling banyak n kali. Ini tidak jelas karena loop masih ditulis sebagai bersarang. Lebih jelas jika kita mengekstraknya:

def disjoint(A, B, C):
  AB = (a
        for a in A
        for b in B
        if a == b)
  ABC = (a
         for a in AB
         for c in C
         if a == c)
  for a in ABC:
    return False
  return True

Varian ini menggunakan generator untuk mewakili hasil antara.

• Dalam generator AB, kita akan memiliki paling banyak n elemen (karena jaminan bahwa daftar input tidak akan mengandung duplikat), dan menghasilkan generator membutuhkan kompleksitas O (n²).
• Memproduksi generator ABCmelibatkan loop atas generator ABdengan panjang n dan Cpanjang n , sehingga kompleksitas algoritmiknya adalah O (n²) juga.
• Operasi ini tidak bersarang tetapi terjadi secara independen, sehingga kompleksitas totalnya adalah O (n² + n²) = O (n²).

Karena pasangan daftar input dapat diperiksa secara berurutan, maka menentukan apakah jumlah daftar yang terpisah dapat dilakukan dalam waktu O (n²).

Analisis ini tidak tepat karena mengasumsikan bahwa semua daftar memiliki panjang yang sama. Kita dapat mengatakan lebih tepat bahwa ABmemiliki min paling panjang (| A |, | B |) dan memproduksinya memiliki kompleksitas O (| A | • | B |). Memproduksi ABCmemiliki kompleksitas O (min (| A |, | B |) • | C |). Kompleksitas total tergantung pada bagaimana daftar input disusun. Dengan | A | ≤ | B | ≤ | C | kita mendapatkan total kompleksitas kasus terburuk O (| A | • | C |).

Perhatikan bahwa kemenangan efisiensi dimungkinkan jika wadah input memungkinkan untuk tes keanggotaan cepat daripada harus mengulangi semua elemen. Ini bisa menjadi kasus ketika mereka diurutkan sehingga pencarian biner dapat dilakukan, atau ketika mereka hash set. Tanpa loop bersarang eksplisit, ini akan terlihat seperti:

for a in A:
  if a in B:  # might implicitly loop
    if a in C:  # might implicitly loop
      return False
return True

atau dalam versi berbasis generator:

AB = (a for a in A if a in B)
ABC = (a for a in AB if a in C)
for a in ABC:
  return False
return True

Perhatikan bahwa jika semua elemen berbeda di setiap daftar yang diasumsikan, Anda dapat mengulangi C hanya sekali untuk setiap elemen dalam A (jika ada elemen dalam B yang sama). Jadi inner loop adalah total O (n ^ 2)

Kami akan menganggap bahwa tidak ada urutan individual yang berisi duplikat.

adalah informasi yang sangat penting.

Kalau tidak, kasus terburuk dari versi yang dioptimalkan masih akan menjadi O (n³), ketika A dan B sama dan mengandung satu elemen yang digandakan n kali:

i = 0
def disjoint(A, B, C):
    global i
    for a in A:
        for b in B:
            if a == b:
                for c in C:
                    i+=1
                    print(i)
                    if a == c:
                        return False 
    return True 

print(disjoint([1] * 10, [1] * 10, [2] * 10))

yang keluaran:

...
...
...
993
994
995
996
997
998
999
1000
True

Jadi pada dasarnya, penulis berasumsi bahwa kasus terburuk O (n³) seharusnya tidak terjadi (mengapa?), Dan "membuktikan" bahwa kasus terburuk sekarang adalah O (n²).

Optimalisasi yang sebenarnya adalah dengan menggunakan set atau dikt untuk menguji inklusi dalam O (1). Dalam hal ini, disjointakan menjadi O (n) untuk setiap input.

Untuk memasukkan hal-hal ke dalam istilah yang digunakan buku Anda:

Saya pikir Anda tidak memiliki masalah memahami bahwa cek untuk a == bkasus terburuk O (n ² ).

Sekarang dalam kasus terburuk untuk loop ketiga, setiap ain Amemiliki kecocokan B, sehingga loop ketiga akan dipanggil setiap waktu. Dalam kasus di mana atidak ada C, itu akan dijalankan melalui seluruh Cset.

Dengan kata lain, ini adalah 1 kali untuk setiap adan 1 kali untuk setiap c, atau n * n. O (n ² )

Jadi ada O (n ² ) + O (n ² ) yang ditunjukkan buku Anda.

Trik dari metode yang dioptimalkan adalah memotong sudut. Hanya jika a dan b cocok, c akan diberikan tampilan yang layak. Sekarang Anda dapat memperkirakan bahwa dalam kasus terburuk Anda masih harus mengevaluasi masing-masing c. Ini tidak benar.

Anda mungkin berpikir kasus terburuknya adalah bahwa setiap cek untuk == b menghasilkan run over C karena setiap cek untuk == b mengembalikan kecocokan. Tetapi ini tidak mungkin karena kondisi untuk ini saling bertentangan. Agar ini berfungsi, Anda membutuhkan A dan B yang berisi nilai yang sama. Mereka mungkin dipesan secara berbeda tetapi setiap nilai dalam A harus memiliki nilai yang cocok dalam B.

Sekarang inilah kickernya. Tidak ada cara untuk mengatur nilai-nilai ini sehingga untuk setiap a Anda harus mengevaluasi semua b sebelum Anda menemukan pasangan Anda.

A: 1 2 3 4 5
B: 1 2 3 4 5

Ini akan dilakukan secara instan karena pencocokan 1 adalah elemen pertama dalam kedua seri. Bagaimana dengan

A: 1 2 3 4 5
B: 5 4 3 2 1

Itu akan bekerja untuk run pertama di atas A: hanya elemen terakhir di B yang akan menghasilkan hit. Tetapi iterasi berikutnya atas A harus sudah lebih cepat karena tempat terakhir di B sudah ditempati oleh 1. Dan memang ini hanya akan mengambil empat iterasi kali ini. Dan ini menjadi sedikit lebih baik dengan setiap iterasi berikutnya.

Sekarang saya bukan ahli matematika jadi saya tidak bisa membuktikan ini akan berakhir di O (n2) tapi saya bisa merasakannya di bakiak saya.

Awalnya bingung, tetapi jawaban Amon sangat membantu. Saya ingin melihat apakah saya dapat melakukan versi yang sangat ringkas:

Untuk nilai tertentu adi A, fungsi membandingkan adengan setiap kemungkinan bdi B, dan itu tidak hanya sekali. Jadi untuk yang diberikan aitu melakukan a == btepat nwaktu.

Btidak mengandung duplikat (tidak ada daftar yang melakukan), jadi untuk yang diberikan aakan ada paling banyak satu pertandingan. (Itulah kuncinya). Di mana ada pertandingan, aakan dibandingkan dengan setiap kemungkinan c, yang berarti a == cdilakukan persis n kali. Di mana tidak ada kecocokan, a == ctidak terjadi sama sekali.

Jadi untuk yang diberikan a, ada nperbandingan, atau 2nperbandingan. Ini terjadi untuk setiap orang a, jadi kasus terbaik yang mungkin (n²) dan yang terburuk adalah (2n²).

TLDR: setiap nilai adibandingkan terhadap setiap nilai bdan terhadap setiap nilai c, tetapi tidak terhadap setiap kombinasi dari bdan c. Kedua masalah ini saling berkaitan, tetapi tidak berlipat ganda.

Pikirkan seperti ini, beberapa angka mungkin dalam dua atau tiga urutan tetapi kasus rata-rata ini adalah bahwa untuk setiap elemen dalam himpunan A, pencarian lengkap dilakukan dalam b. Dijamin bahwa setiap elemen dalam himpunan A akan diulangi tetapi tersirat bahwa kurang dari setengah elemen di himpunan b akan diulangi.

Saat elemen dalam set b diulangi, iterasi terjadi jika ada kecocokan. ini berarti bahwa kasus rata-rata untuk fungsi disjoint ini adalah O (n2) tetapi kasus terburuk absolut untuk itu bisa menjadi O (n3). Jika buku itu tidak merinci, itu mungkin akan memberi Anda kasus rata-rata sebagai jawaban.