J'ai vu ce terme "O(1) access time" utilisé pour signifier "rapidement" mais je ne comprends pas ce qu'il signifie. L'autre terme que je vois avec dans le même contexte est "O(n) access time". Quelqu'un pourrait-il m'expliquer de manière simple ce que ces termes signifient ?
Voir aussi
Vous allez vouloir lire l'Ordre de la complexité.
http://en.wikipedia.org/wiki/Big_O_notation
En bref, O(1) signifie qu'il faut un temps constant, comme 14 nanosecondes, ou trois minutes, quelle que soit la quantité de données dans l'ensemble.
O(n) signifie qu'il faut un temps linéaire avec la taille de l'ensemble, donc un ensemble deux fois plus grand prendra deux fois plus de temps. Vous n'avez probablement pas envie de placer un million d'objets dans l'un de ces ensembles.
En substance, cela signifie qu'il faut le même temps pour rechercher une valeur dans votre collection, que vous ayez un petit nombre d'articles dans votre collection ou un très grand nombre (dans les limites de votre matériel).
O(n) signifie que le temps nécessaire à la recherche d'un élément est proportionnel au nombre d'éléments de la collection.
Les tableaux, auxquels on peut accéder directement, quelle que soit leur taille, et les listes liées, qui doivent être parcourues dans l'ordre depuis le début pour accéder à un élément donné, en sont des exemples typiques.
L'autre opération habituellement discutée est l'insertion. Une collection peut être O(1) pour l'accès mais O(n) pour l'insertion. En fait, un tableau a exactement ce comportement, car pour insérer un élément au milieu, il faudrait déplacer chaque élément vers la droite en le copiant dans l'emplacement suivant.
Toutes les réponses actuelles à cette question vous disent que la O(1) signifie un temps constant (quelle que soit sa mesure ; il peut s'agir du temps d'exécution, du nombre d'opérations, etc.) Ce n'est pas exact.
Dire que le temps d'exécution est O(1) signifie qu'il y a une constante c de telle sorte que le temps d'exécution est borné au-dessus par c indépendant de l'entrée. Par exemple, le retour du premier élément d'un tableau de n entiers est O(1) :
int firstElement(int *a, int n) {
return a[0];
}Mais cette fonction est O(1) aussi :
int identity(int i) {
if(i == 0) {
sleep(60 * 60 * 24 * 365);
}
return i;
}Le temps d'exécution est ici limité à un an, mais la plupart du temps, il est de l'ordre de quelques nanosecondes.
Dire que le temps d'exécution est O(n) signifie qu'il y a une constante c de telle sorte que le temps d'exécution est borné au-dessus par c * n , donde n mesure la taille de l'entrée. Par exemple, trouver le nombre d'occurrences d'un entier particulier dans un tableau non trié de n entiers par l'algorithme suivant est O(n) :
int count(int *a, int n, int item) {
int c = 0;
for(int i = 0; i < n; i++) {
if(a[i] == item) c++;
}
return c;
}Cela est dû au fait que nous devons itérer dans le tableau en inspectant chaque élément un par un.
O(1) ne signifie pas nécessairement "rapidement". Cela signifie que le temps nécessaire est constant, et que no en fonction de la taille de l'entrée de la fonction. La constante peut être rapide ou lente. O(n) signifie que le temps que prend la fonction varie en proportion directe de la taille de l'entrée de la fonction, désignée par n. Là encore, il peut être rapide ou lent, mais il sera de plus en plus lent à mesure que la taille de n augmente.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
