Complejidad de la computación

¿Cuál es la complejidad de la computación ?$n^{n^2},\;n \in \mathbb{N}$

Al usar la transformada rápida de Fourier, las multiplicaciones en los números de bits se pueden hacer en el tiempo (donde la tilde significa que estamos ignorando los factores polilogarítmicos). Al cuadrar repetidamente, podemos calcular con multiplicaciones, y cada multiplicación no implica un número mayor que , que tiene aproximadamente bits. Entonces, la cantidad de tiempo total requerida es .˜ O ( k ) n n 2 O ( log n ) n n 2 n 2 log 2 n ˜ O ( n 2 ( log n ) 2 ) = ˜ O ( n 2$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)$

Editado en respuesta a comentarios El tiempo para calcular se puede descomponer en el tiempo requerido para calcular y el requerido para realizar . Asumiré que multiplicar un número de bits por un número de bits requiere exactamente tiempo por el método del libro escolar; adiciones, etc. son tiempo constante. Como resultado, calcular lleva tiempo.$f(n) = n^{n^2}$$f_1(n) = n^2$$n ^ {f_1(n)}$$m$$n$$mn$$n^2$$\log_2^2 (n)$

Supongamos que usamos exponenciación binaria para calcular . La exponenciación binaria realiza dos tipos de operaciones al calcular : cuadrar el producto actual y multiplicar el producto actual por , según si el bit actual en la expansión binaria de es 0 o 1. En el peor de los casos , es una potencia de dos, de modo que la exponenciación binaria cuadra repetidamente su producto actual hasta que alcanza la respuesta. Tenga en cuenta que tiene bits, de modo que el número de tales cuadrados es . Este es el caso que analizamos más adelante.$f(n)$$f(n)$$n$$n^2$$n^2$$n^2$$m'=\lceil 2 \log_2(n) \rceil$$m= m'-1$

La primera cuadratura lleva tiempo, lo que da como resultado un producto -bit. La segunda cuadratura realiza en dos números de bits y se ejecuta en tiempo, resultando en un producto bits. Continuando, el -ésimo paso lleva tiempo y genera un producto -bit. Este proceso se detiene en el -ésimo paso; Como resultado, lleva tiempo$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$ .

Cuando se incluye el costo inicial de cuadratura, descubrimos que necesitamos tiempo como máximo

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

Nota

• Omití algunos pisos y techos en los cálculos, con la esperanza de que no afectarían materialmente la respuesta.
• Deliberadamente omití un análisis basado en a favor de un límite superior exacto solo para ser riguroso. $O$
• El razonamiento anterior también deja en claro por qué mi análisis anterior fue defectuoso. La notación se usó de manera rápida y flexible, y convenientemente omitió constantes para que, por ejemplo, se convirtiera mágicamente en . ∑ t i O ( log n $O$$\sum t_i$$O(\log n)$
• Las multiplicaciones siempre se pueden acelerar con FFT y otros métodos.