Discussion:Algorithme de Faddeev-Le Verrier

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 $n!$ termes », donc j'ai corrigé). Quelqu'un peut confirmer ? Cygal 4 novembre 2007 à 14:07 (CET)

Tout à fait, la relation de récurrence pour la complexité est $T(n)=n\cdot T(n-1)+{\mathcal {O}}(1)$, en français; la complexité d'un déterminant d'une matrice de taille $n$ peut être vu comme la somme alternée (faisaible une à une en ${\mathcal {O}}(1)$) de $n$ déterminants de matrice de taille $n-1$.

On retrouve bien la relation de récurrence de la factorielle. FlorentPeriat (discuter) 29 juillet 2022 à 05:30 (CEST)

Complexité pivot de Gauss

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