Mengapa mergesort O (log n)?

Mergesort adalah algoritma divide and conquer dan O (log n) karena input berulang kali dibagi dua. Tetapi bukankah seharusnya O (n) karena meskipun input dibelah dua setiap loop, setiap item input harus diulang untuk melakukan swapping pada setiap array yang terbelah dua? Ini pada dasarnya tanpa gejala O (n) dalam pikiran saya. Jika memungkinkan, berikan contoh dan jelaskan bagaimana cara menghitung operasi dengan benar! Saya belum membuat kode apa pun, tetapi saya sudah melihat algoritma online. Saya juga melampirkan gif tentang apa yang digunakan wikipedia untuk secara visual menunjukkan cara kerja mergesort.

Ini O (n * log (n)), bukan O (log (n)). Seperti yang Anda duga dengan akurat, seluruh input harus diulangi, dan ini harus terjadi O (log (n)) kali (input hanya dapat dibelah dua O (log (n)) kali). n item log berulang (n) kali memberi O (n log (n)).

Sudah terbukti bahwa tidak ada jenis perbandingan yang dapat beroperasi lebih cepat dari ini. Hanya jenis yang mengandalkan properti khusus dari input seperti jenis radix yang dapat mengalahkan kompleksitas ini. Faktor konstan dari mergesort biasanya tidak terlalu bagus, jadi algoritma dengan kompleksitas yang lebih buruk seringkali membutuhkan waktu lebih sedikit.

Kompleksitas jenis gabungan adalah O (nlogn) dan BUKAN O (logn).

Merge sort adalah algoritma divide and conquer. Pikirkan hal ini dalam 3 langkah -

1. Langkah membagi menghitung titik tengah dari masing-masing sub-array. Setiap langkah ini hanya membutuhkan waktu O (1).
2. Langkah menaklukkan rekursif mengurutkan dua subarrays dari n / 2 (untuk genap n) elemen masing-masing.
3. Langkah penggabungan menggabungkan n elemen yang membutuhkan O (n) waktu.

Sekarang, untuk langkah 1 dan 3 yaitu antara O (1) dan O (n), O (n) lebih tinggi. Mari kita pertimbangkan langkah 1 dan 3 secara total mengambil O (n). Katakan itu cn untuk beberapa konstanta c.

Berapa kali langkah-langkah ini dijalankan?

Untuk ini, lihat pohon di bawah ini - untuk setiap level dari atas ke bawah Level 2 memanggil metode penggabungan pada 2 sub-array dengan panjang n / 2 masing-masing. Kompleksitas di sini adalah 2 * (cn / 2) = cn Level 3 memanggil metode penggabungan pada 4 sub-array dengan panjang n / 4 masing-masing. Kompleksitas di sini adalah 4 * (cn / 4) = cn dan seterusnya ...

Sekarang, ketinggian pohon ini adalah (logn + 1) untuk n yang diberikan. Dengan demikian kompleksitas keseluruhannya adalah (logn + 1) * (cn). Itu adalah O (nlogn) untuk algoritma pengurutan gabungan.

Kredit gambar: Akademi Khan

Merge Sort adalah algoritma rekursif dan kompleksitas waktu dapat diekspresikan sebagai relasi perulangan berikut.

T (n) = 2T (n / 2) + ɵ (n)

Perulangan di atas dapat dipecahkan dengan menggunakan metode Pohon Perulangan atau metode Master. Itu jatuh dalam kasus II Metode Master dan solusi dari perulangan adalah ɵ (n log n).

Kompleksitas waktu Urutkan Gabung adalah ɵ (nLogn) dalam semua 3 kasus (terburuk, rata-rata dan terbaik) karena jenis gabungan selalu membagi array menjadi dua bagian dan mengambil waktu linear untuk menggabungkan dua bagian.

Ini membagi array input dalam dua bagian, memanggil dirinya untuk dua bagian dan kemudian menggabungkan dua bagian yang diurutkan. Fungsi merg () digunakan untuk menggabungkan dua bagian. Penggabungan (arr, l, m, r) adalah proses utama yang mengasumsikan bahwa arr [l..m] dan arr [m + 1..r] diurutkan dan menggabungkan dua sub-array yang diurutkan menjadi satu. Lihat implementasi C berikut untuk detailnya.

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

Jika kita melihat lebih dekat pada diagram, kita dapat melihat bahwa array secara rekursif dibagi menjadi dua bagian sampai ukuran menjadi 1. Setelah ukuran menjadi 1, proses penggabungan mulai bekerja dan mulai menggabungkan array kembali hingga array lengkap menjadi bergabung.

Algoritma pengurutan berbasis perbandingan memiliki batas yang lebih rendah 𝞨(n*log(n)), yang berarti tidak mungkin memiliki algoritma pengurutan berbasis perbandingan dengan O(log(n))kompleksitas waktu.

By the way, menggabungkan semacam itu O(n*log(n)). Pikirkan seperti ini.

[ a1,a2,         a3,a4,         a5,a6,          a7,a8     .... an-3,an-2,     an-1, an ] 
   \ /            \  /           \ /             \  /            \  /            \  /    
    a1'            a3'            a5'             a7'            an-3'           an-1'    
      \            /                \             /                 \             /
            a1''                          a5''                       an-3''
             \                             /                         /
                          a1'''                                     /
                           \
                                              a1''''

Ini terlihat pohon biner terbalik.

Biarkan ukuran input n.

Masing-masing a_nmewakili daftar elemen. Baris pertama a_nhanya memiliki satu elemen.

Pada setiap tingkat, jumlah biaya gabungan rata-rata adalah n(terdapat kasing sudut yang biayanya lebih rendah [1]). Dan tingginya pohon itu log_2(n).

Jadi, kompleksitas waktu dari jenis gabungan adalah O(n*log_2(n)).

[1] jika mengurutkan pada daftar yang sudah disortir, yang disebut kasus terbaik. biaya berkurang menjadi n/2 + n/4 + n/8 + .... + 1 = 2^log_2(n) -1 ~ O(n). (anggap panjangnya nadalah kekuatan dua)

Penyortiran adalah masalah NP-Complete dalam ilmu komputer (masalah Non Polinomial). Ini berarti bahwa, kecuali jika dibuktikan secara matematis, Anda tidak dapat pergi di bawah O (n log n) saat menyortir daftar elemen.

Periksa artikel ini di Wikipedia ( https://en.wikipedia.org/wiki/P_versus_NP_problem )

Pada dasarnya sejauh ini tidak ada yang berhasil membuktikan bahwa (P == NP) dan jika Anda melakukannya, Anda pertama kali menjadi jutawan, kedua Anda memulai perang dunia III karena fakta bahwa Anda akan dapat memecahkan semua mekanisme keamanan kunci pub / private key yang digunakan di mana-mana saat ini :)