Que signifie «temps d'accès O (1)»?

J'ai vu ce terme «temps d'accès O (1)» qui signifiait «rapidement» mais je ne comprends pas ce que cela signifie. L'autre terme que je vois avec lui dans le même contexte est "O (n) access time". Quelqu'un pourrait-il expliquer de manière simple ce que signifient ces termes?

Voir également

• Qu'est-ce que la notation Big O? L'utilisez vous?
• Big-O pour les enfants de huit ans?

Vous allez vouloir lire sur Ordre de complexité.

http://en.wikipedia.org/wiki/Big_O_notation

En bref, O (1) signifie que cela prend un temps constant, comme 14 nanosecondes, ou trois minutes quelle que soit la quantité de données dans l'ensemble.

O (n) signifie que cela prend un temps linéaire avec la taille de l'ensemble, donc un ensemble deux fois plus grand prendra deux fois le temps. Vous ne voulez probablement pas mettre un million d'objets dans l'un d'entre eux.

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 très très nombreux (dans les contraintes de votre matériel)

O (n) signifierait que le temps nécessaire pour rechercher un élément est proportionnel au nombre d'éléments de la collection.

Des exemples typiques de ceux-ci sont les tableaux, auxquels on peut accéder directement, quelle que soit leur taille, et les listes chaînées, qui doivent être parcourues dans l'ordre depuis le début pour accéder à un élément donné.

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, vous devrez déplacer chaque élément vers la droite en le copiant dans l'emplacement suivant.

Chaque réponse répondant actuellement à cette question vous indique que le O(1)temps constant signifie (quoi qu'il arrive à la mesure; pourrait être le temps d'exécution, le nombre d'opérations, etc.). Ce n'est pas exact.

Dire que le runtime est O(1)signifie qu'il existe une constante ctelle que le runtime est délimité ci-dessus par c, indépendamment de l'entrée. Par exemple, renvoyer le premier élément d'un tableau d' nentiers est O(1):

int firstElement(int *a, int n) {
    return a[0];
}

Mais cette fonction l'est O(1)aussi:

int identity(int i) {
    if(i == 0) {
        sleep(60 * 60 * 24 * 365);
    }
    return i;
}

Le temps d'exécution ici est limité au-dessus d'un an, mais la plupart du temps, le temps d'exécution est de l'ordre de la nanoseconde.

Dire que le runtime est O(n)signifie qu'il existe une constante ctelle que le runtime est délimité ci-dessus par c * n, où nmesure la taille de l'entrée. Par exemple, trouver le nombre d'occurrences d'un entier particulier dans un tableau non trié d' nentiers 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;
}

C'est parce que nous devons parcourir le tableau en inspectant chaque élément un par un.

O (1) signifie que le temps d'accès à quelque chose est indépendant du nombre d'éléments de la collection.

O (N) signifierait que le temps d'accès à un élément est proportionnel au nombre (N) d'éléments de la collection.

O (1) ne signifie pas nécessairement «rapidement». Cela signifie que le temps nécessaire est constant et non basé sur 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 changera en proportion directe de la taille de l'entrée de la fonction, notée n. Encore une fois, cela peut être rapide ou lent, mais cela deviendra plus lent à mesure que la taille de n augmente.

Elle s'appelle la notation Big O et décrit le temps de recherche de divers algorithmes.

O (1) signifie que le temps d'exécution le plus défavorable est constant. Dans la plupart des cas, cela signifie que vous n'avez pas réellement besoin de rechercher dans la collection, vous pouvez trouver ce que vous recherchez tout de suite.

O(1)toujours exécuter dans le même temps quel que soit le jeu de données n. Un exemple de O (1) serait une ArrayList accédant à son élément avec index.

O(n)également connu sous le nom d'ordre linéaire, les performances augmenteront de manière linéaire et proportionnelle à la taille des données d'entrée. Un exemple de O (n) serait une insertion et une suppression ArrayList à une position aléatoire. Comme chaque insertion / suppression ultérieure à une position aléatoire entraînera le décalage des éléments de la ArrayList vers la gauche à droite de son tableau interne afin de maintenir sa structure linéaire, sans parler de la création de nouveaux tableaux et de la copie des éléments de l'ancien à une nouvelle matrice qui prend par conséquent un temps de traitement coûteux, nuit aux performances.

La "notation Big O" est une manière d'exprimer la vitesse des algorithmes. nest la quantité de données avec laquelle l'algorithme travaille. O(1)signifie que, quelle que soit la quantité de données, il s'exécutera en temps constant. O(n)signifie qu'il est proportionnel à la quantité de données.

Fondamentalement, O (1) signifie que son temps de calcul est constant, tandis que O (n) signifie qu'il dépendra linéairement de la taille de l'entrée - c'est-à-dire que le bouclage d'un tableau a O (n) - juste en boucle -, car cela dépend du nombre d'éléments, tout en calculant le maximum entre les nombres ordinaires a O (1).

Wikipedia pourrait également vous aider: http://en.wikipedia.org/wiki/Computational_complexity_theory

Le moyen le plus simple de différencier O (1) et O (n) consiste à comparer tableau et liste.

Pour le tableau, si vous avez la bonne valeur d'index, vous pouvez accéder instantanément aux données. (Si vous ne connaissez pas l'index et devez parcourir le tableau, alors ce ne sera plus O (1))

Pour la liste, vous devez toujours la parcourir, que vous connaissiez l'index ou non.

Voici une analogie simple; Imaginez que vous téléchargez des films en ligne, avec O (1), s'il faut 5 minutes pour télécharger un film, il faudra toujours le même temps pour télécharger 20 films. Ainsi, peu importe le nombre de films que vous téléchargez, ils prendront le même temps (5 minutes), qu'il s'agisse d'un ou de 20 films. Un exemple normal de cette analogie est que lorsque vous allez dans une bibliothèque de films, que vous preniez un ou cinq films, vous les choisirez simplement à la fois. Par conséquent, passer le même temps.

Cependant, avec O (n), s'il faut 5 minutes pour télécharger un film, cela prendra environ 50 minutes pour télécharger 10 films. Le temps n'est donc pas constant ou proportionnel au nombre de films que vous téléchargez.

Cela signifie que le temps d'accès est constant. Que vous accédiez à 100 ou 100 000 enregistrements, le temps de récupération sera le même.

En revanche, le temps d'accès O (n) indique que le temps de récupération est directement proportionnel au nombre d'enregistrements à partir desquels vous accédez.

Cela signifie que l'accès prend un temps constant, c'est-à-dire qu'il ne dépend pas de la taille du jeu de données. O (n) signifie que l'accès dépendra de la taille de l'ensemble de données de manière linéaire.

Le O est également connu sous le nom de big-O.

Introduction aux algorithmes: deuxième édition par Cormen, Leiserson, Rivest & Stein dit à la page 44 que

Puisque toute constante est un polynôme de degré 0, nous pouvons exprimer n'importe quelle fonction constante comme Thêta (n ^ 0) ou Thêta (1). Cette dernière notation est un abus mineur, cependant, car on ne sait pas quelle variable tend vers l'infini. Nous utiliserons souvent la notation Theta (1) pour désigner soit une constante, soit une fonction constante par rapport à une variable. ... On note O (g (n)) ... l'ensemble des fonctions f (n) telles qu'il existe des constantes positives c et n0 telles que 0 <= f (n) <= c * g (n) pour tout n> = n0. ... Notez que f (n) = Thêta (g (n)) implique f (n) = O (g (n)), puisque la notation Thêta est plus forte que la notation O.

Si un algorithme s'exécute en temps O (1), cela signifie qu'il ne dépend pas asymptotiquement d'une variable, ce qui signifie qu'il existe au moins une constante positive qui, multipliée par un, est supérieure à la complexité asymptotique (~ runtime) de la fonction pour des valeurs de n supérieures à un certain montant. Techniquement, c'est l'heure O (n ^ 0).

O (1) signifie accès aléatoire. Dans toute mémoire à accès aléatoire, le temps nécessaire pour accéder à n'importe quel élément à n'importe quel endroit est le même. Ici, le temps peut être n'importe quel entier, mais la seule chose à retenir est le temps nécessaire pour récupérer l'élément à (n-1) ème ou nième emplacement sera le même (c'est-à-dire constant).

Alors que O (n) dépend de la taille de n.

Selon mon point de vue,

O (1) signifie que le temps pour exécuter une opération ou instruction à la fois est un, dans l'analyse de la complexité du temps de l'algorithme pour le meilleur des cas.