DF 2011 Strasbourg

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.

Qu'est-ce que je disais...
On peut certainement le faire en N multiplications... qui chacune peuvent prendre du temps.

"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)) ? :/

Ah...
D'accord...
J'avais pas compris qu'il changeait juste la méthode de multiplication.
Bah pareil que pikrass alors.

Répondre au sujet

Vous devez vous enregistrer ou vous connecter pour poster des messages.