Laufzeitanalyse

Ich weiß also, dass iterierten Logarithmus bedeutet, also = bis .$\log^*$$\log^*(3)$$(\log\log\log\log...)$$n \leq 1$

Ich versuche Folgendes zu lösen:

ist

$\log^*(2^{2^n})$

wenig , wenig oder von$o$$\omega$$\Theta$

${\log^*(n)}^2$

In Bezug auf die inneren Funktionen ist viel größer als , aber das Quadrieren von wirft mich ab.$\log^*(2^{2^n})$$\log^*(n)$$\log^*(n)$

Ich weiß , dass ist , aber ich glaube nicht , dass Eigenschaft für das iterative Logarithmus hält.$\log(n)^2$$O(n)$

Ich habe versucht, die Master-Methode anzuwenden, habe jedoch Probleme mit den Eigenschaften einer -Funktion. Ich habe versucht, n auf max zu setzen (dh ), aber das hat das Problem nicht wirklich vereinfacht.$\log^*(n)$$n = 5$

Hat jemand irgendwelche Tipps, wie ich das angehen soll?

Denken Sie daran, dass wir für per Definition .$k > 1$$\log^*k = \log^*(\log{k}) + 1$

Wenn wir die Definition zweimal anwenden, sehen wir, dass . Jetzt können wir und .$\log^*(2^{2^n}) = \log^*n + 2$$\log^*n + 2$$(\log^*n)^2$

Schreiben wir es auf und sehen, was wir bekommen. Um die Anzahl der Protokolle zu verfolgen, werde ich sie abonnieren. Ich weiß, dass das normalerweise Basis ist. Wenn jemand eine bessere Idee hat, lass es mich wissen oder bearbeite sie in:

$$\log^*(2^{2^n}) \\ = \log_1(\log_2(...\log_k(2^{2^n})...)) \\ = \log_1...\log_{k-1}(2^n\log_{k}(2)) \\ = \log_1...\log_{k-2}(\log_{k-1}(2^n)+\log_{k-1}\log_{k}(2))) \\ = \log_1...\log_{k-2}(n\log_{k-1}(2)+\log_{k-1}\log_{k}(2))) \\ \approx \log_1...\log_{k-2}(n\log_{k-1}(2)) \\ = \log_1...\log_{k-2}(n+\log_{k-1}(2)) \\ \approx \log_1...\log_{k-2}(n) \\ $$ Da wir nach großen suchen , habe ich Die additiven Begriffe und .$n$$\log(\log(2))\approx-0.3665$$\log(2)\approx0.693$

Dies zeigt, dass wenn , dann oder wenn diese kombiniert werden, $\log^*(2^{2^n}) = k$$log^*(n) \approx k-2$

$$\log^*(2^{2^n}) \approx \log^*(n)+2$$

Die großen sind identisch, und wie in den Kommentaren ausgeführt, sind die Gleichungen identisch, wenn die Basis des Logarithmus und die Potenz gleich sind.$\Theta$