J'ai découvert ce problème par la mise en œuvre de l'algorithme de ce message: Exemple de O (n!)? a > J'ai essayé de compter les opérations, et l'algorithme boucle 64 fois lors du calcul de 4! (qui est 24). P> Y a-t-il quelque chose qui me manque? Ou cet algorithme a-t-il vraiment juste une complexité de temps d'exécution qui n'est pas O (n!) P> p>
var operations = 0;
function factorial(n) {
for (let i = 0; i < n; i++) {
operations++;
factorial(n - 1);
}
}
console.log(factorial(4))
console.log('operations: ', operations) // prints 64 operations
3 Réponses :
La fonction factorielle doit être: et c'est O (n).
L'exemple concerne O (n!), Qui est une complexité temporelle dépend de n !, Not N! lui-même.
Cela calculille simplement la factorielle, sa complexité d'exécution n'est pas O (n!)
@Haysstanford Je pensais que vous êtes déroutant si la fonction factorielle est O (n!). J'ai édité la réponse. La fonction dans votre exemple n'est pas nommée factorielle.
Vous comptez des opérations de boucle sur chaque niveau de récursivité (c'est-à-dire des appels de fonction de comptage, à l'exception de la la plus externe), au lieu de compter les appels de fonction les plus profonds. Par conséquent, vous obtenez un nombre beaucoup plus élevé que celui des facteurs simples que vous attendiez: Les expansions d'arbitraire Pour obtenir exactement un factoriel, vous auriez besoin de compter uniquement les appels de fonction les plus internes: P> n code> peuvent être trouvées dans https://oeis.org/a007526 . Celles-ci sont o (n!) Code> strong> mais - voir les formules fermées dans le lien, par exemple. étage (e * n! - 1) code> ou n! * Sum_ {k = 0..n-1} 1 / k! Code>, qui sont clairement dominés par le terme n! Code> terme. (Comptage de toutes les invocations vous donne https://oeis.org/a000522 , n! * Sum_ { k = 0..n} 1 / k! code>). P>
var operations = 0;
function factorial(n) {
if (n == 0) operations++;
for (let i = 0; i < n; i++) {
factorial(n - 1);
}
}
console.log(factorial(4))
console.log('operations: ', operations) // prints 64 operations
Cela compte juste le nombre de factorielle (n) appels lorsque n == 0 . Cela ne se produit qu'à la fin de la boucle, une fois que plusieurs opérations ont été complétées.
@Haysstanford Oui. Et comme ces appels les plus intérieurs sont les plus nombreux, ils dominent la complexité d'exécution. Je voulais juste montrer cela parce qu'il y a exactement n! d'entre eux, car cela semble avoir été le numéro que vous recherchiez.
Il y a probablement une bonne analyse théorique, mais voici un empirique.
J'ai exécuté le programme pour les numéros 0 à 12 et les opérations suivies. Notez que très rapidement les opérations ont tendance à être vraiment proches de n fois l'entrée précédente. Et le ratio d'opérations à n! semble avoir tendance à e. Ainsi, si la limite d'opérations est E (ou une certaine constante) Times N!, Nous sommes O (n!). Nous n'avons pas besoin de = n! faire cela donc.
Cela fait un peu plus de sens, considérant que le Big O a tendance à être une gamme plutôt que le temps d'exécution réel dans tous les cas pour un algorithme.
O (n!) Ne pas vouloir dire n! lui-même. Cela signifie qu'il est proportionnel à n !. Les facteurs factoriels se développent rapidement, il n'est donc pas pratique d'aller très haut, mais peut-être que vous souhaitez table n contre les opérations versus n! et voir si cela rend la relation crédible.