Probleme – Un tableau dynamique, du contrat au coût amorti

1. Le type.

struct tableau_s {
    int* donnees;
    int taille;       /* nombre d'éléments présents */
    int capacite;     /* nombre de cases allouées, capacite >= taille */
};
typedef struct tableau_s tableau;

L'invariant de la structure est écrit dans le commentaire : $0\le \text{taille}\le \text{capacite}$, et donnees pointe sur capacite cases valides.

2. Les opérations.

/* Renvoie un tableau vide de capacité 1, ou NULL en cas d'échec.
   L'appelant devra appeler detruire. */
tableau* creer(void) {
    tableau* t = malloc(sizeof(tableau));
    if (t == NULL) { return NULL; }
    t->donnees = malloc(1 * sizeof(int));
    if (t->donnees == NULL) { free(t); return NULL; }   /* on rend TOUT */
    t->taille = 0;
    t->capacite = 1;
    return t;
}

/* Ajoute x en fin. Renvoie true en cas de succès.
   Précondition : t non nul et bien formé. */
bool ajouter(tableau* t, int x) {
    assert(t != NULL && t->taille <= t->capacite);
    if (t->taille == t->capacite) {                     /* plein : on double */
        int neuve = 2 * t->capacite;
        int* d = malloc((size_t) neuve * sizeof(int));
        if (d == NULL) { return false; }
        for (int i = 0; i < t->taille; i = i + 1) { d[i] = t->donnees[i]; }
        free(t->donnees);
        t->donnees = d;
        t->capacite = neuve;
    }
    t->donnees[t->taille] = x;
    t->taille = t->taille + 1;
    return true;
}

/* Libère t et ses données. Précondition : t vient de creer, ou vaut NULL. */
void detruire(tableau* t) {
    if (t == NULL) { return; }
    free(t->donnees);
    free(t);
}

Remarquer la ligne if (t->donnees == NULL) { free(t); return NULL; } : en cas d'échec partiel, on rend ce qu'on a déjà pris. Sans elle, un échec d'allocation créerait une fuite.

3. Le coût amorti. Un appel isolé peut coûter $\Theta (n)$ : celui qui déclenche la recopie. Mais comptons le total de $n$ ajouts, en partant d'une capacité $1$. Les recopies ont lieu quand la taille atteint $1,2,4,\dots ,2^k$ avec $2^k<n$, et la recopie de rang $j$ coûte $2^j$. Le coût total des recopies vaut donc

$$\sum _{j=0}^{\lfloor {\log }_{2}n\rfloor }{2}^j=2^{\lfloor {\log }_{2}n\rfloor +1}-1<2n.$$

En ajoutant les $n$ écritures elles-mêmes, le total est $<3n=O(n)$, soit un coût amorti de $O(1)$ par ajout.

Pourquoi doubler, et non ajouter une constante. Si l'on agrandissait de $10$ cases à chaque fois, il y aurait $n/10$ recopies, coûtant $10+20+\cdots +n\approx n^2/20$ : le total redeviendrait quadratique. C'est la croissance géométrique qui rend la somme télescopable, et c'est le seul point du raisonnement qui compte.