Français
Menu

Structures de données et algorithmes

Un tableau dynamique, quand on ajoute un élément alors qu'il est plein, alloue une nouvelle zone de capacité double et y copie tous les éléments. Si l'on ajoute un à un 1000 éléments à un tableau vide de capacité 1, combien de copies d'éléments sont effectuées au total ?

  1. A10
  2. B1023
  3. C499 500
Afficher la réponse et l'explication

Réponse : B. 1023

La capacité double à chaque fois qu'elle est atteinte, en passant par 1, 2, 4, …, 512, et à chaque fois tous les éléments présents sont copiés : le nombre total de copies vaut donc 1 + 2 + 4 + … + 512 = 1023. Pour 1000 ajouts, cela fait environ une copie par élément : le coût par ajout est constant en moyenne, soit O(1) amorti. Si la capacité n'augmentait que de 1 à chaque fois, les copies totaliseraient 1 + 2 + … + 999 = 499 500, soit O(n²). 10 est le nombre de réallocations, pas le nombre d'éléments copiés.

S'entraîner sur ce thème Retour au thème

Autres questions sur Structures de données et algorithmes

  1. Pour une table de hachage contenant de nombreux éléments et maintenue à un facteur de charge d'environ 0,5, quelle est la raison la plus appropriée pour laquelle l'adressage ouvert avec sondage linéaire tend à être plus rapide que le chaînage (relier les éléments par des listes chaînées) ?
  2. Des méthodes de tri dont la suite d'étapes de comparaison-échange est fixée d'avance (réseaux de tri), comme le tri bitonique, sont parfois utilisées pour trier sur du matériel parallèle comme les GPU. Pourquoi ?
  3. Pour un tableau de n éléments, quelle est la complexité temporelle d'un traitement qui compare une seule fois chaque paire d'éléments distincts (une double boucle qui compare l'élément i à tous les éléments situés après lui, en faisant avancer i d'un cran à chaque fois) ?
  4. Un programme de complexité temporelle O(n²) met 0,5 seconde pour 1000 données. Combien de temps mettra-t-il environ pour 4000 données ?
  5. Une recherche linéaire compare un à un, depuis le début, les éléments d'un tableau de 100 valeurs distinctes pour trouver une valeur cible. Si la cible se trouve toujours dans le tableau et a la même probabilité d'être à n'importe quelle position, quel est le nombre moyen de comparaisons ?