Qual é a complexidade de$i^i$?

Question

Qual é a complexidade do seguinte algoritmo em Big O:

for(int i = 2; i < n; i = i^i)
{
    ...do somthing
}

Não tenho certeza se existe um operador válido para esse tipo de complexidade. Meu pensamento inicial foi o seguinte:

Depois$k$iterações que queremos: (usando tetração?)

${^{k}i} = n \implies k=\log\log\log..._k\log{n}\implies\mathcal{O(\log\log\log..._k\log{n})}$(onde temos k vezes a função de log), mas não tenho certeza se essa é uma maneira válida de escrever isso. Enfim, temos uma complexidade que inclui$k$, o que não me parece certo.

Answer 1

Esta sequência é OEIS A173566 . Para entender o quão grande ele cresce:

$a_n = 2^{2^{b_{n-1}}}$

Onde:

$b_0 = 0$

$b_n = b_{n-1} + 2^{b_{n-1}}$

A sequência$b_i$cresce mais rápido do que$2^{\cdotp^{\cdotp^{2^0}}}$, onde existem$i$2 na torre.

EXPTIME é$O(2^n)$, 2-EXPTIME é$O(2^{2^n})$, e em geral, você pode definir n-EXPTIME . A sequência$b_i$não está em n-EXPTIME para qualquer n natural. Assim é, e portanto$a_i$, não está na classe de complexidade ELEMENTARY .

A definição acima mostra que$a_i$é primitivo recursivo , o que é interessante, porque significa que não cresce tão rápido quanto a função de Ackermann.

Eu acho (mas realmente não tenho tempo para provar ou refutar formalmente agora) que significa que é$\mathcal{E}^4$na hierarquia Grzegorczyk . Deixo como exercício.

Answer 2

Não existe forma fechada. O número de iterações do loop é 0 se n <= 2, 1 se n <= 4, 2 se n <= 256, 3 se n <=$2^{264}$, 4 se n for menor que algum número com mais de$2^{264}$dígitos, então o universo não é grande o suficiente para anotar esse número.

O verdadeiro problema não é o número de iterações, mas quanto tempo leva para calcular o último i, que obviamente é maior que$n^n$.

Answer 3

Você pode calcular o número de rodadas por uma fórmula recursiva. Encontre um$i$de tal modo que$i^i = n$. Mas nós sabemos que$i = 2^k$. Assim, devemos encontrar um$k$de tal modo que$n =(2^k)^{2^k}$. Por isso,$\log{n} = 2^k \log{2^k} = k \times 2^k$. Agora, se supusermos$n = 2^m$,$m = k\times 2^k = i \log{i}$e$n = 2^{i \log{i}}$. Portanto, se supusermos$T(n)$é a complexidade do método,$T(n) \leq T(\log(n)) + 1$, Como$\log(n) = i \log{i}$e isso significa$i \leq \log{n}$. Por outro lado, sabemos que$\log^*(n) = \log^*(\log n) + 1$. Portanto, podemos concluir que$T(n) = O(\log^*n)$.