Complessità computazionale della conversione di base

Question

Qual è la complessità della conversione di un numero n bit molto grande in una rappresentazione decimale?

Il mio pensiero è che l'algoritmo elementare della divisione intera ripetuta, prendendo il resto per ottenere ogni cifra, avrebbe la complessità O(M(n)log n), dove M(n) è la complessità dell'algoritmo di moltiplicazione; tuttavia, la divisione non è tra 2 numeri n bit ma piuttosto 1 numero bit n e un piccolo numero costante, quindi mi sembra che la complessità potrebbe essere minore.

Answer 1

La conversione di base in Naive come descritto richiede tempo quadratico; fai circa n divisioni bigint-by-smallint, la maggior parte delle quali richiede tempo lineare nella dimensione del bitint n bit.

È possibile eseguire la conversione di base in tempo O (M (n) log (n)), tuttavia, selezionando una potenza di base di destinazione che è approssimativamente la radice quadrata del numero da convertire, facendo dividere e-resto da esso (che può essere fatto in tempo O (M (n)) tramite il metodo di Newton), e ricorsivamente sulle due metà.