Il semble fonctionner très rapidement, même pour des ensembles relativement grands (taille 10). Quelqu'un peut-il me dire le temps d'exécution big-theta de leur algorithme particulier? Je ne peux pas le trouver dans la documentation.Permutations [] runtime dans Mathematica
Ma première tentative pour répondre à cette question était très vicieuse. Comme la plupart des algorithmes internes n'ont pas de comportement de limitation affiché, je décide de le mesurer directement. J'ai mesuré le temps qu'il faut pour calculer le Permutations d'une liste aléatoire de valeurs, et calculé la moyenne et l'écart-type sur 1000 d'entre eux pour chaque longueur. J'ai utilisé une longueur maximale de 10 éléments en raison du temps requis, et que Permutations ne fonctionne que des listes jusqu'à la longueur 12. Mes résultats sur une parcelle de journal:
La moyenne est la ligne noire, et une norme la déviation est représentée par la région remplie entourant la moyenne. À partir de la longueur 5, il est à peu près droit jusqu'à 10 où une légère courbe peut être détectée. Je suppose que c'est O (n!), Mais pour les longueurs inférieures à 7 ou 8, cela n'aura vraiment aucune importance. Même des permutations de longueur 10 ont donné une moyenne respectable de 0,241 ± 0,012 s.
Au lieu de tracer sur une échelle logarithmique, pouvez-vous diviser par 'n!' afin que nous puissions voir à quel point c'est plus lent que ça? – Szabolcs
Je viens de remarquer que * les deux axes sont logarithmiques. Vous vouliez seulement utiliser un axe vertical de journal, non? Sinon, une exponentielle sera courbée vers le haut. – Szabolcs
En supposant une complexité 'n!', Cela devrait donner des temps comparables pour tout 'k', ce qui est le cas pour' k> = 5'. Donc, la complexité est proche de «n!» En effet. Cela donne des temps plus longs pour 'k <5', mais cela pourrait être dû à d'autres effets. 'Table [{k, Premier @ Timing [Do Permutations @ Range [k], {10 * (10!/K!)}];]}, {K, 5, 10}]' – Szabolcs
Pouvez-vous fournir un exemple de WRI met la gestion Big O, Omega, Theta fois de l'un des algorithmes Mathematica dans la documentation? – Simon
Non, mais pour certaines fonctions, elles expliquent les implémentations sous-jacentes (cette fonction appelle une bibliothèque C qui utilise des tables de hachage, etc ...) – JeremyKun
Peut-elle fonctionner plus vite que O (n!) Considérant le nombre d'ensembles générés ? Ou vous êtes intéressé par combien il est plus lent que O (n!)? (Il doit faire des comparaisons supplémentaires, car il ne retournera pas la même chose pour '{1,2,2}' que pour '{1,2,3}'.) – Szabolcs