Il existe un grand nombre d'algorithmes de tri, mais la plupart d'entre eux ne travaillent que sur des ensembles totalement ordonnés, car ils supposent que deux éléments sont comparables. Cependant, existe-t-il de bons algorithmes pour tri des posets, où certains éléments sont inaccessibles? C'est-à-dire, étant donné un ensemble S d'éléments tirés d'une poset, quelle est la meilleure façon de générer une commande x 1 , x 2 , ..., x
3 Réponses :
Je commencerais par le tri de change de sélection. C'est O (n ^ 2) et je ne pense pas que vous ferez mieux que cela.
Il y a un papier intitulé Tri et sélection dans les posets Disponible sur Arxiv.org qui discute des méthodes de tri de commande O ((W ^ 2) Nlog (N / W)), où w est la "largeur" de la posette. Je n'ai pas lu le papier, mais il semble que cela couvre ce que vous recherchez.
Merci pour le lien! Cela a l'air très prometteur!
Télicologique Tri est bien adapté pour trier un ensemble partiellement commandé. La plupart des algorithmes sont O (n ^ 2). Voici un algorithme de Wikipedia:
$ cat brownies.txt preheat bake water mix dry_ingredients mix grease pour mix pour pour bake $ tsort brownies.txt grease dry_ingredients water preheat mix pour bake
N'est-ce pas juste une sorte topologique?
@ jleedev- vous pouvez le faire avec une sorte topologique que si vous saviez comment chaque paire d'éléments de S comparé les uns avec les autres a priori; Sinon, vous devriez dépenser O (| S | ^ 2) Temps de faire toutes les comparaisons.