Coût temps amorti du compteur binaire à coût exponentiel

Question

Si un compteur binaire coûte O (2^i) heure pour changer la valeur du i-ème bit, quelle est la borne supérieure du coût total de n opérations d'incrément?

Answer 1

En supposant que vous démarrez le compteur à zéro,

• n opérations modifier le 1 bit (coût O (n)),
• n/2 opérations changent le 2 bit (coût O (n)),
• n/4 opérations modifient le 4 bits (coût O (n)),
• ...

Cela signifie que le coût est limité par O (n) fois le nombre de nombre total de bits n le compteur, qui est O (log n) car les nombres à n bits ont besoin de O (log n) bits. Par conséquent, la complexité temporelle totale est O (n log n), donc chaque opération a un coût amorti de O (log n).