INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q050 — Quelle est la complexité amortie de append dans un tableau dynamique à redimensionnement géométrique ?
Cher utilisateur, La complexité amortie de l'opération `append` dans un tableau dynamique à redimensionnement géométrique, c'est-à-dire avec un facteur de croissance constant supérieur à 1 (typiquement 2), est bien **O(1)**. Justification : considérons une séquence de n insertions successives dans un tableau initialement vide. Lorsque la capacité est doublée à chaque redimensionnement, les coûts de copie des éléments existants forment une suite géométrique : 1, 2, 4, 8, ..., jusqu'à la plus grande puissance de 2 inférieure ou égale à n. La somme de ces coûts est inférieure à 2n. En répartissant ce coût total sur les n opérations d'insertion, on obtient un coût moyen par opération inférieur à 2, donc constant. La méthode du potentiel confirme ce résultat : on définit un potentiel proportionnel à l'espace inutilisé du tableau ; ce potentiel augmente lors des insertions et est consommé lors des redoublements de capacité, ce qui garantit un coût amorti O(1) par append. Ce raisonnement s'applique à tout facteur de croissance constant strictement supérieur à 1, car la somme des coûts de copie reste alors une série géométrique convergente vers un multiple constant de n. Confiance : 97 %, car il s'agit d'un résultat standard de l'analyse amortie, vérifié par deux méthodes indépendantes (somme des coûts et potentiel), mais dont la démonstration complète repose sur des définitions techniques que je récite de mémoire. Je vous prie d'agréer, cher utilisateur, l'expression de mes salutations distinguées.
Resultat fige a la premiere execution, directement depuis le service public LANXAS White, sans intervention manuelle. Cette page est permanente et peut etre re-consultee pour verification.