Euh... C'est de l'humour Pole4?
Je vois pas pourquoi la complexité ne serait pas O(N).
Pour moi N!= N*N-1*N-2...*1
Sauf si tu parles de l'utilisation pour les complexes. Si c'est le cas, j'en sais rien.
DF 2011 Strasbourg
Qu'est-ce que je disais...
On peut certainement le faire en N multiplications... qui chacune peuvent prendre du temps.
Bon OK, veuillez remplacer le « O(1) » en « une formule », s'il vous plaît \^\^'
Faut se mettre à jour depuis 2007 ;)
Et simplifier O(log log sqrt(N)).
"The asymptotically-best efficiency is obtained by computing n! from its prime factorization. As documented by Peter Borwein, prime factorization allows n! to be computed in time O(n(log n log log n)2), provided that a fast multiplication algorithm is used[...]" (http://en.wikipedia.org/wiki/Factorial)
@Paul : ben alors, elles sont où les divisions par log log sqrt( N )(édité : =O(log log N)) ? :/
Sinon moi en général je considère que la multiplication est en temps constant et j'me fais pas chier. :D
Non mais quelqun peut expliquer de quoi parlent artix et pole4?
Fallait suivre le lien Wikipédia :)
Ah...
D'accord...
J'avais pas compris qu'il changeait juste la méthode de multiplication.
Bah pareil que pikrass alors.
Faut aussi changer l'algo parce que sinon la FFT n'aide pas...
Le bourrin c'est du O(N²log N).