2-yollu birleştirme yaygın Mergesort algoritması bir parçası olarak ele alınır. Ama bir N-bir şekilde gerçekleştirmek en iyi şekilde birleştirme öğrenmek için merak ediyorum?

Diyelim ki, her biri 1 milyon tamsayılar sıralanmış olan N dosyaları var. 100 milyon sıralanan tamsayı olan 1 Tek dosyada birleştirmek için var.

Lütfen bu sorun aslında harici disk tabanlı sıralama için kılıf kullanmak unutmayın. Bu nedenle, gerçek senaryolarda bellek sınırlaması da olacak. Bir anda 2 dosya birleştirme naif bir yaklaşım (99) kez işe yaramaz. Bellek sadece küçük sürgülü bir pencere var ki her dizi için kullanılabilir sağlar.

Eğer zaten bu standart bir çözüm varsa N-yollu birleştirme emin değilim.(Googling bana söyleyecek fazla bir şey almadı.

Ama eğer varsa n-yolu iyi bir algoritma birleştirme eğer biliyorsanız, post algo/link lütfen.

Zaman karmaşıklığı:Eğer biz büyük dosyaları (N) birleştirilecek sayısını artırmak, nasıl böyle bir algoritmanın zaman karmaşıklığı etkiler mi?

Cevaplarınız için teşekkürler.

Her yerde bu bile sormadılar, ama bu ilginç röportajın bir soru olabilir hissettim. Bu nedenle etiketlenmiş.

Nasıl şu fikri hakkında:

1. Öncelik sırası oluşturun
2. Her dosya yinelemef
   1. çifti enqueue(nextNumberİn(f), f)öncelikli olarak ilk değer anahtar kullanarak
3. Sırası boş değil ise
   1. sıradan çıkarma kafa(m, f)sıra
   2. çıktım
   3. eğerfyok tükenmiş
      1. enqueue(nextNumberİn(f), f)

Öncelik sırasına elemanları logaritmik bir şey olabilir ekleyerek bu yana, Madde 2O(N × log N). (Neredeyse tüm) ise yineleme döngü bir eleman ekler bu yana, tüm döngüO(M × log N)neredeMsıralama numaraları sayısıdır.

Tüm dosyaları sayıların boş olmayan bir dizi olduğunu varsayarsakM >Nve böylece bütün algoritma olmalıdırO(M × log N).