Structures de données et algorithmes

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 ?

A2 secondes
B8 secondes
C32 secondes

Afficher la réponse et l'explication

Réponse : B. 8 secondes

En O(n²), le temps de traitement est proportionnel au carré du nombre de données : quatre fois plus de données donnent un temps 4² = 16 fois plus long, soit 0,5 s × 16 = 8 s. 2 secondes correspondrait à O(n), proportionnel au nombre de données, et 32 secondes à O(n³), proportionnel au cube (4³ = 64 fois). En pratique, le traitement peut être encore plus lent, par exemple quand les données ne tiennent plus dans le cache.

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

Autres questions sur Structures de données et algorithmes

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 ?
Par rapport à un tableau, quelle description d'une liste chaînée (liste dont chaque élément contient un pointeur vers l'élément suivant) est correcte ?
Sur une pile vide, on effectue dans cet ordre les opérations push 1, push 2, pop, push 3, push 4, pop, pop. Dans quel ordre les valeurs sont-elles retirées par pop ?
On ajoute dans cet ordre les éléments A, B et C à une file d'attente vide. Ensuite, on retire un élément, on ajoute D et on retire un élément, puis on ajoute E et on retire un élément. Dans quel ordre les éléments sont-ils retirés ?
On évalue l'expression « 3 4 + 2 * 5 − » écrite en notation polonaise inverse (notation postfixée) en empilant chaque nombre sur une pile et, pour chaque opérateur, en retirant deux valeurs, en calculant le résultat et en l'empilant à nouveau. Quel est le résultat ? L'opérande gauche d'un opérateur est la valeur empilée la première.