1439
Siano a e b due interi non negativi, ognuno minore o uguale ad n . Ricordiamo che il numero di bit (cifre binarie) nella rappresentazione binaria di n è circa log2 n. Il numero di operazioni su bit per le quattro operazioni base usando gli algoritmi classici sono elencati nella tabella sottostante.
Operazione su bit | Complessità |
Addizione a+b | O(lg a + lgb) =O(lg n) |
Sottrazione a-b | O(lg a + lgb) =O(lg n) |
Moltiplicazione ab | O((lg a)(lg b)) = O((lg n) 2 ) |
Divisione a =q b + r | O((lg q)(lg b)) = O((lg n) 2 ) |
21 Oct 2005
