Tri en temps linéaire? [fermé]

Question

Etant donné un ensemble d'entrée de n entiers dans l'intervalle [0..n ^ 3-1], fournir un temps linéaire algorithme de tri.

Ceci est un commentaire pour mon test jeudi, et je ne sais pas comment aborder ce problème.

Answer 1

Jetez aussi un coup d'œil à sortes connexes aussi: ou tri compartimenter comptage sorte , ainsi que radix sorte comme mentionné par Pukku.

Answer 2

Jetez un oeil à radix sorte .

Answer 3

Quand les gens disent « algorithme de tri » ils sont souvent référence à « l'algorithme de tri de comparaison », ce qui est tout algorithme qui ne dépend que d'être en mesure de demander « est cette chose plus ou moins que cela. » Donc, si vous êtes limité à poser cette seule question sur les données alors vous ne serez jamais plus n * log (n) (ce qui est le résultat de faire un log (n) recherche du n factoriels ordonnancements possibles d'un ensemble de données) .

Si vous ne pouvez échapper aux contraintes de « comparaison sorte » et poser une question plus sophistiquée d'un morceau de données, par exemple « ce qui est la base 10 radix de ces données », alors vous pouvez venir avec un certain nombre de temps linéaire algorithmes de tri, ils ne prennent plus de mémoire.

Ceci est un commerce de l'espace temps libre. sorte Comparason prend peu ou pas de RAM et fonctionne en N * log (n). sorte radix (par exemple) fonctionne en O (n) et O (log (radix)) mémoire.

Answer 4

wikipedia montre tout à fait différents algorithmes de tri et de leur complexité. vous pouvez les consulter

Answer 5

Il est vraiment simple, si n = 2 et les numéros sont uniques:

• Construction d'une matrice de bits (2 ^ 31-1 bits => ~ 256). initialisez à zéro.
• Lire l'entrée, pour chaque valeur que Déf le bit respectif dans le tableau 1.
• Analyser la matrice, pour chaque ensemble de bits, la sortie de la valeur respective.

Complexité => O (2n)

Dans le cas contraire, utilisez Radix Trier:

Complexité => O (kn) (heureusement)

Answer 6

pense que les chiffres en tant que nombres à trois chiffres dans lequel chaque chiffre compris entre 0 et n-1. Trier ces chiffres avec tri radix. Pour chaque chiffre il y a un appel à compter sorte qui est prise Theta (n + n), de sorte que la durée totale de fonctionnement correspond à Theta (n).

Answer 7

un ensemble d'une gamme limitée de numéros peut être représenté par une image bitmap de bits de gamme. Dans ce cas, une image bitmap 500mb, donc pour quoi que ce soit, mais d'énormes listes, vous seriez mieux avec Radix Trier. Comme vous rencontrez le nombre k, réglez bitmap [k] = 1. traversal unique par liste, O (N).

Answer 8

Alike algo est possible:

M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];

Il est possible pour seul algo complexité linéaire, mais il a complexité O (k * N) par vérin (N - nombre d'éléments de tableau, k - len de l'élément)