Notation grand O, algorithmes de tri et de recherche courants, et schémas de récursivité testés en entretien technique et en cours.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- Que mesure la notation grand O ?
Show answer
La façon dont le temps d'exécution ou l'espace mémoire requis par un algorithme augmente à mesure que la taille de l'entrée croît.- Définissez la complexité temporelle O(1).
Show answer
Temps constant : le temps d'exécution ne change pas, quelle que soit la taille de l'entrée.- Définissez la complexité temporelle O(n).
Show answer
Temps linéaire : le temps d'exécution croît proportionnellement à la taille n de l'entrée.- Définissez la complexité temporelle O(log n).
Show answer
Temps logarithmique : le temps d'exécution croît avec le logarithme de la taille de l'entrée.- Définissez la complexité temporelle O(n^2).
Show answer
Temps quadratique : le temps d'exécution croît avec le carré de la taille de l'entrée.- Définissez la complexité temporelle O(n log n).
Show answer
Temps linéarithmique : le temps d'exécution est n multiplié par le logarithme de n.- Définissez la complexité temporelle O(2^n).
Show answer
Temps exponentiel : le temps d'exécution double à chaque augmentation de la taille de l'entrée.- Quelle est la complexité temporelle de l'accès à un élément d'un tableau par son indice ?
Show answer
O(1), temps constant.- Quelle est la complexité temporelle de la recherche d'une valeur dans un tableau non trié ?
Show answer
O(n), temps linéaire.- Quelle est la complexité temporelle de la recherche binaire dans un tableau trié ?
Show answer
O(log n), temps logarithmique.- Que doit-on garantir à propos d'un tableau avant de pouvoir utiliser la recherche binaire ?
Show answer
Le tableau doit être trié.- Quelle est la complexité temporelle de l'insertion d'un élément au début d'un tableau ?
Show answer
O(n), temps linéaire.- Quelle est la complexité temporelle de l'ajout d'un élément à la fin d'un tableau dynamique qui a encore de la capacité ?
Show answer
O(1) amorti, temps constant.- Quelle est la complexité temporelle moyenne d'une recherche dans une table de hachage ?
Show answer
O(1), temps constant, avec une bonne fonction de hachage.- Quelle est la complexité temporelle du tri rapide (quicksort) dans le cas moyen ?
Show answer
O(n log n), temps linéarithmique.
FlashKeepers