Menggabungkan Dua Daftar Terurut

Sebuah Algoritma RAM yang optimal akan membuat satu elemen dalam satu waktu. Algoritma ini memerlukan paling banyak n – 1 buah perbandingan untuk menggabungkan 2 (dua) buah Daftar Terurut yang berukuran n/2. Kompleksitas waktunya \inline \Theta (n). Sedangkan algoritma PRAM hanya membutuhkan \inline \Theta (log \: n) dengan sebuah prosesor untuk setiap elemennya. Dua daftar yang sudah terurut yang akan digabungkan ini memiliki elemen-elemen yang saling disjoint.

(Merging Two Sorted List – Quinn)

merging_two_sorted_list_Quinn_1

 

merging_two_sorted_list_Quinn_2

Leave a Reply

Your email address will not be published.

Captcha Captcha Reload