Obliczeniowa złożoność konwersji bazy

Question

Jaka jest złożoność konwersji bardzo dużej liczby n-bitowej na reprezentację dziesiętną?

Moja myśl jest taka, że ​​elementarny algorytm powtarzanego podziału całkowitoliczbowego, pobierający pozostałość w celu uzyskania każdej cyfry, miałby złożoność O(M(n)log n), gdzie M(n) jest złożonością algorytmu mnożenia; jednak podział nie jest między liczbami 2 n-bitowymi, ale raczej n-bitową liczbą i małą stałą liczbą, więc wydaje mi się, że złożoność może być mniejsza.

Answer 1

Naiwna konwersja bazy, jak opisano, zajmuje kwadratowy czas; wykonujesz około n podziałów bigint-by-smallint, z których większość zajmuje czas liniowy w rozmiarze n-bitowego biginta.

Konwersję bazy można przeprowadzić w czasie O (M (n) log (n)), wybierając moc bazy docelowej, która jest w przybliżeniu pierwiastkiem kwadratowym liczby konwertowanej do konwersji, dzieląc- i - pozostała przez niego (można to zrobić w czasie O (M (n)) za pomocą metody Newtona) i recursing na dwóch połówkach.