Complexité du programme factoriel récursif

Si vous prenez la multiplication O(1) oui, O(N) est correct. Toutefois, notez que la multiplication de deux nombres de longueur arbitraire xO(1) non matériel --x tend vers l'infini, le temps nécessaire à la multiplication augmente (par exemple si vous utilisez multiplication de Karatsuba, c'est O(x ** 1.585)).

Vous pouvez théoriquement faire mieux pour suffisamment grand nombre Schönhage-Strassen, mais j'avoue que j' Je n'ai aucune expérience réelle avec celui-là.