Comment décririez-vous le temps d'exécution de ce genre, étant donné une fonction sorted qui retourne True si la liste est triée qui fonctionne dans O (n):Temps de course aléatoire Trier
def sort(l):
while not sorted(l): random.shuffle(l)
Supposons brassage est parfaitement au hasard.
Serait-ce écrit en notation big-O? Ou existe-t-il un autre moyen de catégoriser les algorithmes avec des composants aléatoires?
Cet algorithme est appelé Bogosort. C'est une instance d'une classe d'algorithmes appelée Las Vegas Algorithms. Les algorithmes de Las Vegas sont Randomized Algorithms qui garantissent toujours des résultats corrects mais ne donnent aucune garantie sur les ressources informatiques.
La complexité temporelle de Bogosort ne peut pas être directement exprimée en Bachmann-Landau Notation, en raison de sa nature probabiliste. Cependant, nous pouvons faire une déclaration au sujet de sa complexité temporelle expected. La complexité temporelle attendue de Bogosort est O(n·n!).
Croyez-le ou non, il y a une entrée de wiki pour cela: http://en.wikipedia.org/wiki/Bogosort
cas moyen: (! N * N) O
Et "Le pire des cas: infini" –
Mais le pire des cas a la probabilité 0, ce qui est une bonne nouvelle pour la moyenne :-) –
Le pire des cas est très improbable, cependant. Mais le cas moyen est encore nul :-) – tgamblin
notation Big-O suppose le pire des scénarios. Dans le pire des cas, cet algorithme ne se termine jamais.
Il finira par se terminer, puisque le aléatoire aléatoire est vraiment aléatoire (selon la description du problème), il finira par donner le shuffle correct. – SoapBox
Non, SoapBox, pour que cet algorithme soit garanti de se terminer, la fonction aléatoire doit être garantie pour produire un ordre particulier (le trié).Mais s'il a la garantie de produire cet ordre, alors ce n'est pas vraiment aléatoire. –
Si le shuffle est vraiment aléatoire, il y a toujours un cas qui est pire qu'un cas donné. Il y a un cas qui prendra un milliard de cycles; il y a un cas qui prendra 10^10^10^10^10 cycles. Le "pire" cas est pire que les deux! Ergo ça ne finit jamais. – Artelius
Le cas moyen est en effet O (N N!):
Observe qu'il ya exactement N! permutations de N éléments. La probabilité de choisir le bon est exactement 1/N !. Par conséquent, par la loi forte des grands nombres, le nombre attendu de shuffles est N !.
D'où vient l'autre facteur N? Vous devez vérifier, à chaque étape, quelle permutation vous avez choisie. Cela peut être fait linéairement en comparant les éléments adjacents. Par conséquent un facteur supplémentaire de N.
Commentaires ci-dessus ont indiqué que O (g (n)) notation est "pire des cas":
1) Ce n'est pas vrai. La définition de O (g (n)) est: f (n) est O (g (n)) s'il existe quelques c, d tels que f (n) < c * g (n) + d pour suffisamment grand n. Il n'y a rien sur le "pire des cas". Il se trouve juste que g (n) est une fonction plus grande que f (n), mais la pure définition mathématique ne dit rien de "cas".
2) Pour les algorithmes randomisés, il est inutile de faire une analyse du "pire cas". Vous pouvez arriver à une exécution qui va être vraiment mauvaise.
3) Les exécutions vraiment mauvaises se produisent sur un ensemble de mesure 0 (Un probabiliste dirait qu'elles "presque sûrement" n'arrivent pas). Ils sont réellement impossibles à observer.
" Ils sont réellement impossibles à observer. " - par exemple, bien au-delà des discussions philosophiques sur la question de savoir si un générateur aléatoire est ou non garanti pour produire chaque sortie dans sa gamme, parce que vous mourriez en premier ;-) –
Mais l'algorithme ne vérifie pas les permutations précédentes peut répéter indéfiniment. – shinzou
Big O est la notation asymptotique la plus couramment utilisée, ce qui signifie que n se rapproche de l'infini. Certes, comme n se rapproche de l'infini, il y a encore une chance que le tout premier shuffle triera le deck ... Mais en réalité, plus le n est grand, moins il est probable qu'il reviendra dans n * n! temps. Je dirais que c'est O (l'infini). Cela dit, les algorithmes de Las Vegas n'ont pas de notation standard Bachmann-Landau. –
Donc c'est polynomial? Comment cela n'est-il pas au moins exponentiel? – shinzou
Shinzou 'n * n!' Est beaucoup plus grand 'n^2'. C'est plus gros que exponentiel. Donc, où 'n^2' signifie' n \ * n'; l'équation ici 'n * n!' signifie 'n * (n * (n-1) * (n-2) * (n-3) * (n-4) * ... * (n- (n- 1))) ' –