Sortir Radix & Efisiensi O(N log N).

Saya telah belajar tentang Radix sort baru-baru ini dan salah satu sumber yang saya gunakan adalah halaman Wikipedia. Saat ini ada paragraf berikut mengenai efisiensi algoritma:

Topik efisiensi pengurutan radix dibandingkan dengan algoritma pengurutan lainnya agak rumit dan menimbulkan banyak kesalahpahaman. Apakah pengurutan radix sama efisiennya, kurang efisien, atau lebih efisien dibandingkan algoritma berbasis perbandingan terbaik bergantung pada detail asumsi yang dibuat. Kompleksitas pengurutan radix adalah O(wn) untuk n kunci yang merupakan bilangan bulat dengan ukuran kata w. Kadang-kadang w disajikan sebagai sebuah konstanta, yang akan membuat pengurutan radix lebih baik (untuk n yang cukup besar) daripada algoritma pengurutan berbasis perbandingan terbaik, yang semuanya melakukan perbandingan O(n log n) untuk mengurutkan n kunci. Namun, secara umum w tidak dapat dianggap sebagai sebuah konstanta: jika semua n kunci berbeda, maka w setidaknya harus berupa log n agar mesin akses acak dapat menyimpannya dalam memori, sehingga memberikan paling banter kompleksitas waktu O(n log n). Hal ini tampaknya membuat pengurutan radix sama efisiennya dengan pengurutan berbasis perbandingan terbaik (dan lebih buruk lagi jika kunci lebih panjang daripada log n) .

Sayangnya, bagian yang dicetak tebal menjadi hambatan yang tidak dapat saya lewati. Saya memahami bahwa secara umum pengurutan Radix adalah O(wn), dan melalui sumber lain telah melihat bagaimana O(n) dapat dicapai, tetapi tidak dapat memahami mengapa n kunci berbeda memerlukan waktu O(n log n) untuk penyimpanan secara acak- mesin akses. Saya cukup yakin bahwa ini adalah soal matematika sederhana, namun sayangnya pemahaman yang kuat masih berada di luar jangkauan saya.

Upaya terdekat saya adalah sebagai berikut:

Diberikan suatu bilangan pokok 'B' dan sebuah bilangan dalam bilangan pokok tersebut, 'N', maka angka maksimum yang dapat dimiliki 'N' adalah:

(logB dari N) + 1.

Jika setiap nomor dalam daftar tertentu, L, adalah unik, maka kita mempunyai:

L *((logB dari N) + 1) kemungkinan

Pada titik ini saya tidak yakin bagaimana kemajuannya.

Adakah yang bisa memperluas bagian di atas yang dicetak tebal dan menjelaskan mengapa n kunci berbeda memerlukan minimal log n untuk penyimpanan akses acak?


sorting big-o radix-sort
person Levenal    schedule 25.01.2018    source sumber

Jawaban (1)


arrow_upward
0
arrow_downward

Dengan asumsi pengurutan radix MSB dengan m bins konstan:

  • Untuk tipe data berukuran besar yang harus mengakomodasi setidaknya n nilai berbeda, jumlah bit yang diperlukan adalah N = ceiling(log2(n))
  • Jadi jumlah memori yang dibutuhkan untuk menyimpan setiap nilai juga O(log n); dengan asumsi akses memori berurutan, kompleksitas waktu membaca/menulis suatu nilai adalah O(N) = O(log n), meskipun dapat menggunakan pointer sebagai gantinya
  • Jumlah digitnya adalah O(N / m) = O(log n)
  • Yang penting, setiap digit berurutan harus berbeda pangkat 2, yaitu m juga harus pangkat 2; asumsikan ini cukup kecil untuk platform HW, mis. Digit 4-bit = 16 nampan

Selama penyortiran:

  • Untuk setiap lintasan radix, yang jumlahnya O(log n):

    1. Count each bucket: get the value of the current digit using bit operations - O(1) for all n values. Should note that each counter must also be N bits, although increments by 1 will be (amortized) O(1). If we had used non-power-of-2 digits, this would in general be O(log n log log n) ( source )

    2. Jadikan susunan jumlah keranjang bersifat kumulatif: harus melakukan m - 1 penambahan, yang masing-masing adalah O(N) = O(log n) (tidak seperti kasus khusus kenaikan)

    3. Tulis larik keluaran: ulangi nilai n, tentukan bin lagi, dan tulis penunjuk dengan offset yang benar

Jadi kompleksitas totalnya adalah O(log n) * [ n * O(1) + m * O(log n) + n * O(1) ] = O(n log n).

person meowgoesthedog    schedule 25.01.2018
comment
Terima kasih atas jawabannya. Mengenai poin ke 4, apakah itu hanya komentar umum saja? Sejauh yang saya tahu, Radix sort tidak melakukan perbandingan apa pun - person Levenal; 26.01.2018
comment
@Levenal maaf, jelas My_Brain.exe has encountered a problem and has to close. - person meowgoesthedog; 26.01.2018
comment
Bolehkah saya menyarankan reboot =) Editannya sangat membantu, terima kasih. Menguraikannya seperti yang Anda lakukan akan membuatnya lebih mudah untuk diselesaikan. Saya belum memahami semuanya, tetapi sekarang saya lebih percaya diri untuk mencapainya. - person Levenal; 26.01.2018