Qual è la complessità di$i^i$?

Question

Qual è la complessità del seguente algoritmo in Big O:

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

Non sono sicuro che esista un operatore valido per questo tipo di complessità. Il mio pensiero iniziale è stato il seguente:

Dopo$k$iterazioni che vogliamo: (usando la tetrazione?)

${^{k}i} = n \implies k=\log\log\log..._k\log{n}\implies\mathcal{O(\log\log\log..._k\log{n})}$(dove abbiamo k volte la funzione log) ma non sono sicuro che questo sia un modo valido per scriverlo. Ad ogni modo, abbiamo una complessità che include$k$, cosa che non mi sembra giusta.

Answer 1

Questa sequenza è OEIS A173566 . Per capire quanto cresce:

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

dove:

$b_0 = 0$

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

La sequenza$b_i$cresce più velocemente di$2^{\cdotp^{\cdotp^{2^0}}}$, dove ci sono$i$2 è nella torre.

EXPTIME è$O(2^n)$, 2-EXPTIME è$O(2^{2^n})$e, in generale, puoi definire n-EXPTIME . La sequenza$b_i$non è in n-EXPTIME per nessun n naturale. Quindi, e quindi$a_i$, non è nella classe di complessità ELEMENTARY .

La definizione di cui sopra lo dimostra$a_i$è primitivo ricorsivo , il che è interessante, perché ciò significa che non cresce così velocemente come la funzione di Ackermann.

Penso (ma non ho davvero il tempo di provare o smentire formalmente in questo momento) che significhi che lo è$\mathcal{E}^4$nella gerarchia di Grzegorczyk . Lasciato per esercizio.

Answer 2

Non esiste una forma chiusa. Il numero di iterazioni del ciclo è 0 se n <= 2, 1 se n <= 4, 2 se n <= 256, 3 se n <=$2^{264}$, 4 se n è minore di un numero con più di$2^{264}$cifre, quindi l'universo non è abbastanza grande per scrivere quel numero.

Il vero problema non è il numero di iterazioni, ma quanto tempo ci vuole per calcolare l'ultima i, che ovviamente è maggiore di$n^n$.

Answer 3

Puoi calcolare il numero di round con una formula ricorsiva. Trova un$i$tale che$i^i = n$. Ma lo sappiamo$i = 2^k$. Quindi, dovremmo trovare a$k$tale che$n =(2^k)^{2^k}$. Quindi,$\log{n} = 2^k \log{2^k} = k \times 2^k$. Ora, se supponiamo$n = 2^m$,$m = k\times 2^k = i \log{i}$e$n = 2^{i \log{i}}$. Quindi, se supponiamo$T(n)$è la complessità del metodo,$T(n) \leq T(\log(n)) + 1$, come$\log(n) = i \log{i}$e significa$i \leq \log{n}$. D'altra parte, lo sappiamo$\log^*(n) = \log^*(\log n) + 1$. Pertanto, possiamo concludere che$T(n) = O(\log^*n)$.