Doğrusal zamanda sıralama

Question

Algoritmaların 2. baskısına giriş okuyorum, ve bir soru var ki n tamsayılarını, 0 ile n arası -1 arasında lineer zamanda sıralayabiliyoruz. IBM'in çapsal sıralama yaklaşımı düşünüyorum. En az anlamlı basamakla başlarım, en az anlamlı rakamlara göre ayrı sayıları alıyorum ve sonra sıralayın, sonra bir sonraki en az anlamlı basamağa göre ayırın. Her ayrıştırma O (n) zamanını alır. Ancak, şüphesiz, örneğin, sayılardan biri n basamaktan oluşuyorsa, o zaman algoritma O (1 * n + 2 * n + ... + n * n) = O (n) zamanını alır, sağ? Sayıların n haneden daha az oluşundan emin olabilir miyiz, ya da kimse soru için başka bir ipucu verebilir mi? Teşekkürler

Answer 1

Radix Sıralama karmaşıklığı, d ile bir sayıdaki basamak sayısı olarak O(dn)'dir.

Algoritma yalnızca d sabit olduğunda doğrusal modda çalışır! Sizin durumunuzda d = 3log(n) ve algoritmanız O(nlog(n))'da çalışacaktır.

Doğruluğunda bu sorunu nasıl çözeceğimi bilmiyorum. Sayıların doğasıyla ilgili başka bir bilgi parçacığı var mıdır? Sayıların doğasıyla ilgili herhangi bir bilginin eksik olup olmadığını merak ediyorum ...

Answer 2

Bir kelime RAM modeli varsayarsak, ve o, N'ye uyuyor. (1) kelimeler, doğrusal bir zaman algoritması vardır.

Her sayıyı baz n'ye yazın ve bir yarıçap sıralaması yapın (sayım sıralamasının durağan bir sayım türüyle birlikte).

Sınırsız n'yi varsayalım, daha sonra giriş kütüğünün büyüklüğünü, n '' n '' n '' n '' (n = n (n = n) ') tekrar işleyecektir. Doğrusal zaman algoritması! (Tabii ki, sanırım bunu hala aritmetik olduğunu varsayalım O (1) ...)