Complexidade da computação

Qual é a complexidade da computação ?$n^{n^2},\;n \in \mathbb{N}$

Usando a transformação rápida de Fourier, as multiplicações nos números de bits de podem ser feitas no tempo (onde o til significa que estamos ignorando os fatores polilogarítmicos). Ao quadrado repetido, podemos calcular com multiplicações, e cada multiplicação envolve nenhum número maior que , que possui aproximadamente bits. Portanto, a quantidade total de tempo necessária é .˜ 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 em resposta a comentários O tempo para calcular pode ser decomposto no tempo necessário para calcular f 1 ( n ) = n 2 e no tempo necessário para executar n f 1 ( n ) . Assumirei que multiplicar um número de m bits por um número de n bits leva exatamente m n tempo pelo método do livro escolar; adições, etc. são de tempo constante. Como resultado, a computação n 2 leva o log $f(n) = n^{n^2}$$f_1(n) = n^2$$n ^ {f_1(n)}$$m$$n$$mn$$n^2$tempo.$\log_2^2 (n)$

Suponha que usamos exponenciação binária para calcular . A exponenciação binária realiza dois tipos de operações na computação de : quadratura do produto atual e multiplicação do produto atual por n , dependendo se o bit atual na expansão binária de n 2 é 0 ou 1. No pior caso, n 2 é uma potência de dois, de modo que a exponenciação binária esquadria repetidamente seu produto atual até chegar à resposta. Observe que n 2 tem m ′ = ⌈ 2 log 2 ( n ) ⌉f ( n $f(n)$$f(n)$$n$$n^2$$n^2$$n^2$$m'=\lceil 2 \log_2(n) \rceil$bits, de modo que o número desses quadrados seja . Este é o caso que analisamos mais adiante.$m= m'-1$

O primeiro quadrado leva tempo, resultando em um produto o 1 = 2 log 2 ( n ) -bit. O segundo quadrado recebe dois números de 1 o bit e é executado em t 2 = o 2 1 vez, resultando em um produto de o 2 = 2 o 1 bits. Continuando, a i- ésima etapa leva t i = 4 i - 1$t_1=\log_2^2(n)$$o_1=2 \log_2(n)$$o_1$$t_2=o_1^2$$o_2=2o_1$$i$tempo e emite umoi=2ilog2(N)produto de bits. Esse processo para nam-ésima etapa; como resultado, leva tempo$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$

Quando o custo quadrático inicial é incluído, achamos que precisamos de tempo no máximo

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

Nota

• Omiti alguns pisos e tetos nos cálculos, esperando que eles não afetassem materialmente a resposta.
• Omiti deliberadamente uma análise baseada em em favor de um limite superior exato, apenas para ser rigoroso. $O$
• O raciocínio acima também deixa claro por que minha análise anterior foi falha. O notação foi utilizado de uma forma solta rápido-e-e-lo convenientemente omitido constantes de modo que, por exemplo, Σ t i mágica tornou-se O ( log n ) . $O$$\sum t_i$$O(\log n)$
• As multiplicações podem ser sempre aceleradas pela FFT e outros métodos.