Problème — Le compteur binaire, et son coût amorti

1. L'incrémentation.

/* Incremente le compteur binaire c[0..k-1] (c[0] est le bit de poids
   faible). Renvoie false en cas de debordement.
   Precondition : chaque c[i] vaut 0 ou 1. */
bool incrementer(int c[], int k) {
    int i = 0;
    /* INVARIANT : les bits c[0..i-1] valaient tous 1 et ont ete mis a 0. */
    while (i < k && c[i] == 1) { c[i] = 0; i = i + 1; }
    if (i == k) { return false; }        /* le compteur etait 11...1 */
    c[i] = 1;
    return true;
}

Pire cas d'un appel : le compteur vaut $11\dots 1$ sur ses $k$ bits utiles, et l'incrémentation les bascule tous, plus un : $\Theta (k)=\Theta (\log n)$. Mesuré : le $256^{\text{e}}$ incrément, qui passe de $11111111$ à $100000000$, coûte $9$ basculements.

2. Le coût total, par comptage par bit. Ne comptons pas par incrémentation, mais par bit — c'est le retournement qui fait tout le problème.

• Le bit $0$ bascule à chaque incrémentation : $n$ fois.
• Le bit $1$ ne bascule qu'une incrémentation sur deux : $\lfloor n/2\rfloor$ fois.
• Plus généralement, le bit $j$ bascule $\lfloor n/2^j\rfloor$ fois.

Le total vaut donc

$$\sum _{j\ge 0}\lfloor \frac{n}{2^j}\rfloor \le \sum _{j\ge 0}\frac{n}{2^j}=2n.$$

Le coût amorti d'une incrémentation est donc $<2$, c'est-à-dire $O(1)$ — alors que le pire cas d'un appel isolé est $\Theta (\log n)$.

3. La mesure, et la formule exacte.

      n | basculements | 2n - s2(n) | basculements/n
      1 |            1 |          1 | 1,0000
      2 |            3 |          3 | 1,5000
      4 |            7 |          7 | 1,7500
     16 |           31 |         31 | 1,9375
    100 |          197 |        197 | 1,9700
   1000 |         1994 |       1994 | 1,9940
  10000 |        19995 |      19995 | 1,9995
1000000 |      1999993 |    1999993 | 2,0000

La valeur exacte est $2n-s_2(n)$, où $s_2(n)$ est le nombre de $1$ dans l'écriture binaire de $n$ — la mesure la confirme sur les huit lignes. Le rapport monte vers $2$ sans jamais l'atteindre : la borne $2n$ est fine, et elle est stricte.