Discussion:Algorithme de Faddeev-Le Verrier

Dernier commentaire : il y a 1 an par FlorentPeriat
Autres discussions [liste]
  • Admissibilité
  • Neutralité
  • Droit d'auteur
  • Article de qualité
  • Bon article
  • Lumière sur
  • À faire
  • Archives
  • Commons

L'algorythme "naïf" n'est-il pas de complexité factorielle vu qu'il faut faire n! sommes (qui est beaucoup plus grand que e^n)?

En effet, et l'article se contredisait (« s'écrit comme somme de termes », donc j'ai corrigé). Quelqu'un peut confirmer ? Cygal 4 novembre 2007 à 14:07 (CET)Répondre

Tout à fait, la relation de récurrence pour la complexité est , en français; la complexité d'un déterminant d'une matrice de taille peut être vu comme la somme alternée (faisaible une à une en ) de déterminants de matrice de taille .
On retrouve bien la relation de récurrence de la factorielle. FlorentPeriat (discuter) 29 juillet 2022 à 05:30 (CEST)Répondre

Complexité pivot de Gauss

modifier

La complexité temporelle du pivot de Gauss est effectivement en  , cependant on travaillera ici avec des polynômes de taille   comme coefficients (additionnés et multipliés par un scalaire en temps linéaire), on obtiendra dans ce cas une complexité de  . Ce facteur   viendra aussi léser notre complexité en espace de   à  . FlorentPeriat (discuter) 29 juillet 2022 à 05:24 (CEST)Répondre

Revenir à la page « Algorithme de Faddeev-Le Verrier ».