Le redimensionnement et son coût amorti

(a)

def inserer_auto(table: list, cle, valeur) -> list:
    inserer(table, cle, valeur)
    # Si le facteur de charge dépasse 0.75
    if taille(table) > 0.75 * len(table):
        # Créer une nouvelle table deux fois plus grande
        nouvelle_table = creer(2 * len(table))
        # Réinsérer tous les éléments (les adresses changent !)
        for alveole in table:
            for c, v in alveole:
                inserer(nouvelle_table, c, v)
        return nouvelle_table
    return table

(b) La courbe représentant le temps d'exécution cumulé en fonction du nombre d'insertions $n$ est globalement rectiligne (croissance linéaire), indiquant un coût moyen par insertion constant. Cette droite est parsemée de petits sauts verticaux (des à-coups) de taille de plus en plus grande, se produisant lors des doublements de la table. (c) Soit une table de taille finale $2^K$. Au cours des redimensionnements successifs, le nombre total d'insertions (de re-hachages) induit par les agrandissements est : $$\text{Couˆt}=0,75\times (2^0+2^1+2^2+\cdots +2^{K-1})=0,75\times (2^K-1)<0,75\times 2^K$$ Comme le nombre final d'éléments $n$ vérifie $n>0,75\times 2^{K-1}$ (car le dernier redimensionnement s'est produit pour dépasser ce seuil), on a $0,75\times 2^K<2n$. Le nombre total de copies est donc strictement majoré par $2n$, ce qui prouve que la complexité cumulée du redimensionnement est bien en $O(n)$. Sur $n$ insertions, le coût amorti par insertion est de $O(n)/n=O(1)$.