Complexité du calcul

Quelle est la complexité du calcul ?$n^{n^2},\;n \in \mathbb{N}$

En utilisant la transformée de Fourier rapide, les multiplications sur les nombres à bits peuvent être effectuées dans le temps (où le tilde signifie que nous ignorons les facteurs polylogarithmiques). Par la mise au carré répétée, nous pouvons calculer avec multiplications, et chaque multiplication n'implique aucun nombre supérieur à , qui a environ bits. Ainsi, le temps total requis est .$k$$\tilde{O}(k)$$n^{n^2}$$O(\log n)$$n^{n^2}$$n^2 \log_2 n$$\tilde{O}(n^2(\log n)^2)=\tilde{O}(n^2)$

Modifié en réponse aux commentaires Le temps de calcul peut être décomposé en le temps requis pour calculer et celui requis pour effectuer . Je suppose que la multiplication d'un nombre bits par un nombre bits prend exactement temps par la méthode du livre scolaire; les ajouts, etc. sont à temps constant. Par conséquent, le calcul de prend du temps .$f(n) = n^{n^2}$$f_1(n) = n^2$$n ^ {f_1(n)}$$m$$n$$mn$$n^2$$\log_2^2 (n)$

Supposons que nous utilisons l'exponentiation binaire pour calculer . L'exponentiation binaire effectue deux types d'opérations dans le calcul de : la mise au carré du produit actuel et la multiplication du produit actuel par , selon que le bit actuel dans l'expansion binaire de est 0 ou 1. Dans le pire des cas , est une puissance de deux, de sorte que l'exponentiation binaire place à plusieurs reprises son produit actuel jusqu'à ce qu'il atteigne la réponse.Notez que a bits, de sorte que le nombre de ces équerrages est . C'est le cas que nous analysons plus loin.$f(n)$$f(n)$$n$$n^2$$n^2$$n^2$$m'=\lceil 2 \log_2(n) \rceil$$m= m'-1$

Le premier quadrillage prend temps, résultant en un produit bits. La seconde mise au carré prend deux bits et s'exécute en fois, résultant en un produit bits. En continuant, la ème étape prend fois et un produit bits. Ce processus s'arrête à la -ième étape; en conséquence, cela prend du temps$t_1=\log_2^2(n)$$o_1=2 \log_2(n)$$o_1$$t_2=o_1^2$$o_2=2o_1$$i$$t_i = 4^{i-1}\log^2_2 n$$o_i=2^{i} \log_2 (n)$$m$

$T _{exp} =\sum _{[1..m]} t_i = \log_2 ^2 (n) \sum_{[1..m]} 4^i = \frac{4^m -1} {3} \log_2 ^2 n$ .

Lorsque le coût de mise au carré initial est inclus, nous constatons que nous avons besoin de temps au maximum

${T_{exp} + \log_2^2{n}}$

Remarque

• J'ai omis certains planchers et plafonds dans les calculs, en espérant qu'ils n'affecteraient pas matériellement la réponse.
• J'ai délibérément omis une analyse basée sur en faveur d'une limite supérieure exacte juste pour être rigoureuse. $O$
• Le raisonnement ci-dessus montre également pourquoi mon analyse antérieure était erronée. La notation été utilisée de manière rapide et lâche, et elle a commodément omis des constantes de sorte que, par exemple, est devenu par magie . $O$$\sum t_i$$O(\log n)$
• Les multiplications peuvent toujours être accélérées par la FFT et d'autres méthodes.