n*log(n)
Mengenai ini, apa kompleksitas waktu kasus terbaik dari jenis gabungan?
Gabungkan sort
|
Contoh pengurutan gabungan. Pertama bagi daftar menjadi unit terkecil (1 unsur), lalu bandingkan setiap unsur dengan daftar yang berdekatan untuk mengurutkan dan menggabungkan dua daftar yang berdekatan. Akhirnya semua unsur diurutkan dan digabungkan. |
|
|
Kelas |
Algoritma pengurutan |
|
Struktur data |
Himpunan |
|
Performa terburuk |
O(n log n) |
Selain di atas, algoritma pengurutan mana yang memiliki kompleksitas terbaik? Untuk Pengurutan Penyisipan Kasus Terbaik dan Pengurutan Heap adalah yang Terbaik karena kompleksitas waktu proses kasus terbaik mereka adalah O(n). Untuk kasus rata-rata kompleksitas waktu berjalan asimtotik terbaik adalah O(nlogn) yang diberikan oleh Merge Sort, Heap Sort, Quick Sort. Untuk Kasus Terburuk, kompleksitas run time terbaik adalah O(nlogn) yang diberikan oleh Merge Sort, Heap Sort.
Juga pertanyaannya adalah, apa kompleksitas dari merge sort?
Kompleksitas dari merge sort adalah O(nlogn) dan BUKAN O(logn). Setiap langkah ini hanya membutuhkan waktu O(1). Langkah taklukkan secara rekursif mengurutkan dua subarray masing-masing n/2 (untuk n genap). Langkah penggabungan menggabungkan n unsur yang membutuhkan waktu O(n).
Di mana jenis gabungan digunakan?
Merge Sort : digunakan dalam skenario database, karena stabil (multi-key sort ) dan eksternal (hasil tidak semua muat di memori). Berguna dalam skenario terdistribusi di mana data tambahan tiba selama atau setelah penyortiran. Konsumsi memori mencegah penggunaan yang lebih luas pada perangkat kecil, tetapi versi Nlog^2N di tempat memang ada.
