Prouvez n! est entièrement constructible en temps

Nous venons de terminer notre leçon "Constructibilité du temps" en classe la semaine dernière, et nous avons, par exemple, montré que $n^k, 2^n$ sont entièrement constructibles dans le temps, c'est-à-dire qu'il existe une machine de Turing (déterministe multi-bandes) $n$ donné, s'arrête après exactement $f(n)$ étapes, et a simplement demandé si nous pouvions maintenant prouver que $n!$ est entièrement constructible dans le temps (et déplacé).

Je ne sais pas comment va la preuve, mais je pense qu'elle doit utiliser $n^k$ constructibilité temporelle dans une certaine mesure, ou une certaine identité impliquant des factorielles, puisque nous avons montré $n^k$ est (entièrement) temps constructible en utilisant $n^k = n + \sum_{i=1}^{i=k-1}(n - 1)n^i$.

Des conseils seraient également appréciés, vraiment. Merci d'avance.

Supposons que nous ayons trouvé $n!$ en entrée $n$. Notre complexité est en termes de longueur de l'entrée (nous supposons qu'elle est$L=O(logn)$). Multiplication d'un$k$ peu à peu $l$ nombre de bits via la multiplication standard prend $O(kl)$ opérations (également après multiplication du nombre de bits dans la résultante si $O(k+l)$). Nous multiplions linéairement dans une boucle de$1$ à $n$ obtenir $n!$. Donc, le nombre d'opérations effectuées est limité par$\# = L^2 ( 1 + 2 ...(n-1) ) = \frac{L^2n(n-1)}{2} = O(L^22^{O(L)})=o(L!)$. Il est donc constructible d'espace et de temps.