Quelle est la complexité de $i^i$?

Question

Quelle est la complexité de l'algorithme suivant dans Big O :

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

Je ne sais pas s'il existe un opérateur valide pour ce type de complexité. Ma première pensée était la suivante :

Après$k$itérations que nous voulons : (en utilisant la tétration ?)

${^{k}i} = n \implies k=\log\log\log..._k\log{n}\implies\mathcal{O(\log\log\log..._k\log{n})}$(où nous avons k fois la fonction log) mais je ne suis pas sûr que ce soit une manière valable d'écrire ceci. Quoi qu'il en soit, nous avons une complexité qui inclut$k$, ce qui ne me semble pas correct.

Answer 1

Cette séquence est OEIS A173566 . Pour comprendre à quel point il grandit :

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

où:

$b_0 = 0$

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

La séquence$b_i$croît plus vite que$2^{\cdotp^{\cdotp^{2^0}}}$, où il y a$i$2 dans la tour.

EXPTIME est$O(2^n)$, 2-EXPTIME est$O(2^{2^n})$, et en général, vous pouvez définir n-EXPTIME . La séquence$b_i$n'est pas dans n-EXPTIME pour tout n naturel. Donc, et donc$a_i$, n'appartient pas à la classe de complexité ELEMENTARY .

La définition ci-dessus montre que$a_i$est récursif primitif , ce qui est intéressant, car cela signifie qu'il ne croît pas aussi vite que la fonction d'Ackermann.

Je pense (mais je n'ai pas vraiment le temps de prouver ou de réfuter formellement pour le moment) cela signifie que c'est$\mathcal{E}^4$dans la hiérarchie de Grzegorczyk . Laissé comme exercice.

Answer 2

Il n'y a pas de formulaire fermé. Le nombre d'itérations de la boucle est 0 si n <= 2, 1 si n <= 4, 2 si n <= 256, 3 si n <=$2^{264}$, 4 si n est inférieur à un certain nombre avec plus de$2^{264}$chiffres, donc l'univers n'est pas assez grand pour écrire ce nombre.

Le vrai problème n'est pas le nombre d'itérations, mais le temps qu'il faut pour calculer le dernier i, qui est évidemment plus grand que$n^n$.

Answer 3

Vous pouvez calculer le nombre de tours par une formule récursive. Trouver un$i$tel que$i^i = n$. Mais nous savons que$i = 2^k$. Par conséquent, nous devrions trouver un$k$tel que$n =(2^k)^{2^k}$. Ainsi,$\log{n} = 2^k \log{2^k} = k \times 2^k$. Maintenant, si nous supposons$n = 2^m$,$m = k\times 2^k = i \log{i}$et$n = 2^{i \log{i}}$. Ainsi, si l'on suppose$T(n)$est la complexité de la méthode,$T(n) \leq T(\log(n)) + 1$, comme$\log(n) = i \log{i}$et cela signifie$i \leq \log{n}$. D'autre part, nous savons que$\log^*(n) = \log^*(\log n) + 1$. Par conséquent, nous pouvons conclure que$T(n) = O(\log^*n)$.