Złożoność obliczeń

Jaka jest złożoność obliczeń ?$n^{n^2},\;n \in \mathbb{N}$

Dzięki szybkiej transformacie Fouriera mnożenie liczb bitowych może być wykonane w czasie ˜ O ( k ) (gdzie tylda oznacza , że ignorujemy czynniki polilogarytmiczne). Przez powtarzanie kwadratu możemy obliczyć n n 2 z mnożeniem O ( log n ) , a każde mnożenie obejmuje liczbę większą niż n n 2 , która ma z grubsza n 2 log 2 n bitów. Zatem całkowity wymagany czas wynosi ˜ 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)$

Edytowane w odpowiedzi na komentarze Czas obliczenia można rozłożyć na czas wymagany do obliczenia f 1 ( n ) = n 2 i czas wymagany do wykonania n f 1 ( n ) . Zakładam, że pomnożenie liczby m bitów przez liczbę n bitów zajmuje dokładnie m n czasu metodą podręcznika szkolnego; dodatki itp. są stałym czasem. W rezultacie obliczenie n 2 zajmuje log $f(n) = n^{n^2}$$f_1(n) = n^2$$n ^ {f_1(n)}$$m$$n$$mn$$n^2$czas.$\log_2^2 (n)$

Załóżmy, że do obliczania używamy potęgowania binarnego . Potęgowanie binarne wykonuje dwa rodzaje operacji przy obliczaniu f ( n ) : podniesienie kwadratu bieżącego produktu i pomnożenie bieżącego produktu przez n , w zależności od tego, czy bieżący bit w rozwinięciu binarnym n 2 wynosi 0 czy 1. W najgorszym przypadku n 2 jest potęgą dwóch, tak że potęgowanie binarne wielokrotnie kwadratuje bieżący iloczyn, aż osiągnie odpowiedź. Zauważ, że n 2 ma m ′ = ⌈ 2 log 2 ( $f(n)$$f(n)$$n$$n^2$$n^2$$n^2$ bitów, tak że liczba takich kwadratów wynosi m = m ′ - 1 . Jest to przypadek, który analizujemy poniżej.$m'=\lceil 2 \log_2(n) \rceil$$m= m'-1$

Pierwsze podniesienie do kwadratu zajmuje czas , co daje iloczyn o 1 = 2 log 2 ( n ) -bit. Drugie kwadraty przyjmują dwie liczby o 1 bit i biegną w czasie t 2 = o 2 1 , co daje iloczyn o 2 = 2 o 1- bit. Kontynuując, i- ty krok zajmuje 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$czas i wyjścia aoi=2ilog2(n)-bitowy produkt. Proces ten zatrzymuje się nam-tymetapie; w rezultacie wymaga czasu$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$

Po uwzględnieniu początkowego kosztu do kwadratu potrzebujemy czasu

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

Uwaga

• W obliczeniach pominąłem niektóre podłogi i sufity, mając nadzieję, że nie wpłyną one znacząco na odpowiedź.
• Celowo pominąłem analizę opartą na na korzyść dokładnej górnej granicy, żeby być rygorystycznym. $O$
• Powyższe rozumowanie wyjaśnia również, dlaczego moja wcześniejsza analiza była wadliwa. oznaczenie stosowano w szybki i-luźny sposób, i korzystnie pominięta stałe tak, że na przykład, Σ T i magiczną się O ( log n ) . $O$$\sum t_i$$O(\log n)$
• Mnożenie można zawsze przyspieszyć za pomocą FFT i innych metod.