Komplexität der Berechnung

Was ist die Komplexität der Berechnung ?$n^{n^2},\;n \in \mathbb{N}$

Mit der schnellen Fourier-Transformation können Multiplikationen mit Bit-Zahlen in der Zeit ˜ O ( k ) durchgeführt werden (wobei die Tilde anzeigt, dass wir polylogarithmische Faktoren ignorieren). Durch wiederholtes Quadrieren können wir n n 2 mit O ( log n ) -Multiplikationen berechnen , und jede Multiplikation beinhaltet keine Zahl größer als n n 2 , die ungefähr n 2 log 2 n Bits hat. Die Gesamtzeit beträgt also ˜ 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)$

Als Antwort auf Kommentare bearbeitet Die Zeit zum Berechnen von kann in die Zeit zerlegt werden, die zum Berechnen von f 1 ( n ) = n 2 erforderlich ist, und die Zeit, die zum Ausführen von n f 1 ( n ) erforderlich ist . Ich gehe davon aus, dass das Multiplizieren einer m- Bit-Zahl mit einer n- Bit-Zahl nach der Schulbuchmethode genau m n Zeit benötigt. Ergänzungen usw. sind konstante Zeit. Als Ergebnis der Berechnung n 2 nimmt log $f(n) = n^{n^2}$$f_1(n) = n^2$$n ^ {f_1(n)}$$m$$n$$mn$$n^2$Zeit.$\log_2^2 (n)$

Angenommen, wir verwenden die binäre Exponentiation zur Berechnung von . Die binäre Exponentiation führt bei der Berechnung von f ( n ) zwei Arten von Operationen aus : Quadrieren des aktuellen Produkts und Multiplizieren des aktuellen Produkts mit n , je nachdem, ob das aktuelle Bit in der binären Erweiterung von n 2 0 oder 1 ist. Im schlimmsten Fall n 2 ist eine Zweierpotenz ist , so daß binäre Potenzierung wiederholt Quadrate seine aktuelle Produkt , bis er die answer.Note erreicht , dass n 2 ist m ' = ⌈ 2 log 2 ( $f(n)$$f(n)$$n$$n^2$$n^2$$n^2$ Bits, so dass die Anzahl solcher Quadrate m = m ' - 1 ist . Dies ist der Fall, den wir weiter unten analysieren.$m'=\lceil 2 \log_2(n) \rceil$$m= m'-1$

Das erste Quadrieren dauert , was zu einem o 1 = 2 log 2 ( n ) -Bit-Produkt führt. Das zweite Quadrieren nimmt zwei o 1 -Bit-Zahlen auf und läuft in t 2 = o 2 1- mal, was zu einem o 2 = 2 o 1- Bit-Produkt führt. Wenn Sie fortfahren, dauert der i- te Schritt 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$Zeit und gibt einoi=2ilog2(n)-Bit-Produkt aus. Dieser Vorgang stoppt beimm-ten Schritt; Infolgedessen braucht es Zeit$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$

Wenn die anfänglichen Quadrierungskosten enthalten sind, brauchen wir höchstens Zeit

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

Hinweis

• Ich habe einige Böden und Decken in den Berechnungen weggelassen, in der Hoffnung, dass sie die Antwort nicht wesentlich beeinflussen würden.
• $O$
• $O$$\sum t_i$$O(\log n)$
• Die Multiplikationen können immer durch FFT und andere Methoden beschleunigt werden.