it-swarm-id.com

Mengapa menggabungkan waktu run case terburuk terburuk O (n log n)?

Dapatkah seseorang menjelaskan kepada saya dalam bahasa Inggris yang sederhana atau cara yang mudah untuk menjelaskannya?

50
adit

Pada semacam gabungan "tradisional", masing-masing melewati data menggandakan ukuran subbagian yang diurutkan. Setelah lulus pertama, file akan disortir menjadi beberapa bagian dengan panjang dua. Setelah umpan kedua, panjang empat. Kemudian delapan, enam belas, dll hingga ukuran file.

Perlu untuk menggandakan ukuran bagian yang disortir sampai ada satu bagian yang terdiri dari seluruh file. Diperlukan lg (N) penggandaan ukuran bagian untuk mencapai ukuran file, dan setiap lintasan data akan memakan waktu sebanding dengan jumlah catatan.

31
supercat

The Gabungkan Sortir menggunakan Divide-and-Conquer pendekatan untuk menyelesaikan masalah penyortiran. Pertama, ia membagi input menjadi dua menggunakan rekursi. Setelah membelah, itu mengurutkan setengah dan menggabungkan mereka menjadi satu output yang diurutkan. Lihat gambar

MergeSort recursion tree

Ini berarti lebih baik untuk mengurutkan setengah dari masalah Anda terlebih dahulu dan melakukan penggabungan sederhana subrutin. Jadi, penting untuk mengetahui kerumitan subrutin gabungan dan berapa kali akan disebut dalam rekursi.

Pseudo-code untuk jenis gabungan benar-benar sederhana.

# C = output [length = N]
# A 1st sorted half [N/2]
# B 2nd sorted half [N/2]
i = j = 1
for k = 1 to n
    if A[i] < B[j]
        C[k] = A[i]
        i++
    else
        C[k] = B[j]
        j++

Sangat mudah untuk melihat bahwa dalam setiap loop Anda akan memiliki 4 operasi: k ++ , i ++ atau j ++ , jika pernyataan dan atribusi C = A | B . Jadi Anda akan memiliki operasi kurang dari atau sama dengan 4N + 2 memberikan O (N) kompleksitas. Demi bukti, 4N + 2 akan diperlakukan sebagai 6N, karena berlaku untuk N = 1 ( 4N +2 <= 6N ).

Jadi anggap Anda memiliki input dengan [~ # ~] n [~ # ~] elemen dan menganggap [~ # ~] n [~ # ~] adalah kekuatan 2. Pada setiap level Anda memiliki subproblem dua kali lebih banyak dengan input dengan setengah elemen dari input sebelumnya. Ini berarti bahwa pada level j = 0, 1, 2, ..., lgN akan ada 2 ^ j sub-masalah dengan input panjang N/2 ^ j . Jumlah operasi di setiap level j akan kurang atau sama dengan

2 ^ j * 6 (N/2 ^ j) = 6N

Perhatikan bahwa tidak masalah level Anda akan selalu memiliki operasi 6N yang kurang atau sama.

Karena ada level lgN + 1, kompleksitasnya akan menjadi

O(6N * (lgN + 1)) = O(6N*lgN + 6N) = O(n lgN)

Referensi:

65
Davi Sampaio

Ini karena apakah itu merupakan kasus terburuk atau rata-rata jenis penggabungan hanya membagi array menjadi dua bagian pada setiap tahap yang memberikannya komponen lg (n) dan komponen N lainnya berasal dari perbandingannya yang dibuat pada setiap tahap. Jadi menggabungkannya menjadi hampir O (nlg n). Tidak masalah apakah kasus rata-rata atau kasus terburuk, faktor lg (n) selalu ada. Istirahat N faktor tergantung pada perbandingan yang dibuat yang berasal dari perbandingan yang dilakukan dalam kedua kasus. Sekarang kasus terburuk adalah kasus di mana perbandingan N terjadi untuk input N pada setiap tahap. Jadi itu menjadi O (nlg n).

20
Pankaj Anand

Setelah memisahkan array ke tahap di mana Anda memiliki elemen tunggal yaitu menyebutnya sublists,

  • pada setiap tahap kami membandingkan elemen setiap sublist dengan sublist yang berdekatan. Misalnya, [Reusing @ Davi's image]

    enter image description here

    1. Pada Tahap-1 setiap elemen dibandingkan dengan yang berdekatan, jadi perbandingan n/2.
    2. Pada Tahap-2, setiap elemen sublist dibandingkan dengan sublist yang berdekatan, karena setiap sublist diurutkan, ini berarti bahwa jumlah maksimum perbandingan yang dibuat antara dua sublist adalah <= panjang sublist yaitu 2 (pada Tahap-2) dan 4 perbandingan di Tahap-3 dan 8 di Tahap-4 karena panjang daftar berlipat ganda. Yang berarti jumlah maksimum perbandingan pada setiap tahap = (panjang sublist * (jumlah sublists/2)) ==> n/2
    3. Seperti yang telah Anda amati, jumlah total tahapan adalah log(n) base 2 Jadi kompleksitas totalnya adalah == (jumlah maksimum perbandingan pada setiap tahap * jumlah tahapan) = = O ((n/2) * log (n)) ==> O (nlog (n))
18
blueskin

Algoritma menggabungkan-mengurutkan urutan S ukuran n dalam waktu O (n log n), dengan asumsi dua elemen S dapat dibandingkan dalam O(1) waktu . enter image description here

8
Andrii Glukhyi

Pohon rekursif akan memiliki kedalaman log(N), dan pada setiap level dalam pohon itu Anda akan melakukan pekerjaan gabungan N untuk menggabungkan dua array yang diurutkan.

Menggabungkan array yang diurutkan

Untuk menggabungkan dua array yang diurutkan A[1,5] Dan B[3,4] Anda cukup mengulang keduanya mulai dari awal, memilih elemen terendah antara dua array dan menambah pointer untuk array itu. Anda selesai ketika kedua pointer mencapai akhir dari array masing-masing.

[1,5] [3,4]  --> []
 ^     ^

[1,5] [3,4]  --> [1]
   ^   ^

[1,5] [3,4]  --> [1,3]
   ^     ^

[1,5] [3,4]  --> [1,3,4]
   ^      x

[1,5] [3,4]  --> [1,3,4,5]
    x     x

Runtime = O(A + B)

Gabungkan semacam ilustrasi

Tumpukan panggilan rekursif Anda akan terlihat seperti ini. Pekerjaan dimulai pada simpul daun bawah dan gelembung naik.

beginning with [1,5,3,4], N = 4, depth k = log(4) = 2

  [1,5]    [3,4]     depth = k-1 (2^1 nodes) * (N/2^1 values to merge per node) == N
[1]  [5]  [3]  [4]   depth = k   (2^2 nodes) * (N/2^2 values to merge per node) == N

Dengan demikian Anda melakukan N bekerja di setiap level k di pohon, di mana k = log(N)

N * k = N * log(N)

4
geg

Banyak jawaban lain yang bagus, tapi saya tidak melihat penyebutan tinggi dan kedalaman terkait dengan contoh "merge-sort tree". Inilah cara lain untuk mendekati pertanyaan dengan banyak fokus pada pohon. Berikut gambar lain untuk membantu menjelaskan: enter image description here

Hanya rekap: seperti jawaban lain telah menunjukkan kita tahu bahwa pekerjaan menggabungkan dua irisan diurutkan dari urutan berjalan dalam waktu linier (fungsi pembantu gabungan yang kita panggil dari fungsi penyortiran utama).
Sekarang melihat pohon ini, di mana kita dapat menganggap setiap keturunan root (selain root) sebagai panggilan rekursif ke fungsi penyortiran, mari kita coba menilai berapa banyak waktu yang kita habiskan pada setiap node .. Karena pengurutan urutan dan penggabungan (keduanya bersamaan) mengambil waktu linier, waktu berjalan dari setiap node adalah linier sehubungan dengan panjang urutan di simpul itu.

Di sinilah kedalaman pohon masuk. Jika n adalah ukuran total dari urutan asli, ukuran urutan di setiap simpul adalah n/2saya, di mana saya adalah kedalaman. Ini ditunjukkan pada gambar di atas. Menyatukan ini dengan jumlah kerja linear untuk setiap irisan, kami memiliki waktu berjalan O (n/2saya) untuk setiap simpul di pohon. Sekarang kita hanya perlu menjumlahkannya untuk n node. Salah satu cara untuk melakukan ini adalah mengenali bahwa ada 2saya node pada setiap level kedalaman di pohon. Jadi untuk level apa pun, kita memiliki O (2saya * n/2saya), yang O(n) karena kita dapat membatalkan 2sayas! Jika setiap kedalaman adalah O (n), kita hanya perlu mengalikannya dengan tinggi dari pohon biner ini, yang merupakan logn. Jawaban: O (nlogn)

referensi: Struktur Data dan Algoritma dengan Python

3
trad

Algoritma MergeSort mengambil tiga langkah:

  1. Divide langkah menghitung posisi tengah sub-array dan butuh waktu konstan O (1).
  2. Taklukkan langkah rekursif mengurutkan dua sub array sekitar n/2 elemen masing-masing.
  3. Combine langkah menggabungkan total n elemen pada setiap pass yang membutuhkan paling banyak n perbandingan sehingga dibutuhkan O (n).

Algoritma ini memerlukan kira-kira log masuk untuk mengurutkan array elemen n dan sehingga total waktu kompleksitas adalah nlogn.

2
MisterJoyson