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

https://stackoverflow.com/questions/697918

big-o

22-08-2019
|

Question

Je l'ai vu ce terme « O (1) temps d'accès » utilisé pour signifier « rapidement » mais je ne comprends pas ce que cela signifie. L'autre terme que je vois avec elle dans le même contexte est « O (n) temps d'accès ». Quelqu'un pourrait-il expliquer s'il vous plaît de manière simple ce que signifient ces termes?

Voir aussi


Quelle est la notation Big O? Avez-vous l'utiliser?

Big-O pour huit ans de

La solution

Vous allez vouloir lire sur ordre de complexité.

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

En bref, O (1) signifie qu'il faut une constante de temps, comme 14 nanosecondes, ou trois minutes quelle que soit la quantité de données dans le jeu.

O (n) signifie qu'il faut une quantité linéaire du temps avec la taille de l'ensemble, donc un ensemble deux fois la taille aura deux fois le temps. Vous ne voulez probablement pas mettre un million d'objets dans l'un de ces derniers.

Autres conseils

En substance, cela signifie qu'il faut la même quantité de temps pour rechercher une valeur dans votre collection si vous avez un petit nombre d'éléments dans votre collection ou très très nombreux (dans les limites de votre matériel)

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

Des exemples typiques de ces tableaux sont, qui peuvent être accessibles directement, quelle que soit leur taille, et les listes chaînées, qui doivent être parcourus pour le début d'accéder à un élément donné.

L'autre opération généralement discuté est d'insérer. 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 à droite en le copiant dans la fente suivante.

Chaque réponse répondre actuellement à cette question vous indique que le O(1) signifie constante de temps (tout ce qui arrive à mesurer, pourrait être l'exécution, le nombre d'opérations, etc.). Ce ne sont pas précis.

Dire que l'exécution est O(1) signifie qu'il y a un c constant de telle sorte que le moteur d'exécution est délimitée ci-dessus par c, indépendamment de l'entrée. Par exemple, le retour du premier élément d'un tableau d'entiers de n 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 moteur d'exécution ici est limitée au-dessus de 1 an, mais la plupart du temps le temps d'exécution est de l'ordre de la nanoseconde.

Dire que l'exécution est O(n) signifie qu'il y a un c constant de telle sorte que le moteur d'exécution est délimitée ci-dessus par c * n, où n mesure la taille de l'entrée. Par exemple, trouver le nombre d'occurrences d'un nombre entier particulier dans un tableau d'entiers non triés de n 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;
}

Ceci est parce que nous devons parcourir le tableau inspecter chaque élément un à la fois.

O (1) signifie que le temps pour accéder à quelque chose est indépendant du nombre d'articles de la collection.

O (N) signifierait le temps pour accéder à un élément est proportionnelle au nombre (N) d'éléments de la collection.

O (1) ne signifie pas nécessairement "rapidement". Cela signifie que le temps qu'il faut est constant et pas en fonction de la taille de l'entrée à la fonction. Constant pourrait être rapide ou lent. O (n) signifie que le temps prend la fonction change en proportion directe avec la taille de l'entrée à la fonction, notée n. Encore une fois, il pourrait être rapide ou lent, mais il devenir plus lent que la taille n augmente.

Il est appelé notation Big O , et décrit le temps de recherche de différents algorithmes.

O (1) signifie que le pire temps d'exécution de cas est constant. Pour la plupart, cela signifie que la situation vous ne acctually besoin de chercher la collection, vous cand trouver ce que vous recherchez tout de suite.

« notation Big O » est un moyen d'exprimer la vitesse des algorithmes. n est la quantité de données que l'algorithme travaille. O(1) signifie que, peu importe la façon dont beaucoup de données, il exécute en temps constant. O(n) signifie qu'elle est proportionnelle à la quantité de données.

O(1) exécuter toujours dans le même temps, quel que soit n ensemble de données. Un exemple de O (1) serait un ArrayList accès à son élément d'index.

O(n) également connu sous l'ordre linéaire, la performance va croître de façon linéaire et en proportion directe avec la taille des données d'entrée. Un exemple de O (n) serait une insertion et de suppression ArrayList à la position aléatoire. Comme chaque insertion ultérieure / suppression à la position aléatoire provoquera les éléments du ArrayList à décalage à droite à gauche de son tableau interne afin de maintenir sa structure linéaire, sans parler de la création d'un nouveau tableau et la copie des éléments de l'ancien à nouveau tableau qui prend le temps de traitement coûteux par conséquent, le préjudice porté la performance.

Fondamentalement, O (1) signifie que le temps de calcul est constant, tout en O (n) signifie qu'il dépendra linéairement sur la taille de l'entrée - à savoir une boucle à travers un réseau a O (n) - juste en boucle -, car il dépend du nombre d'éléments, tout en calculant le maximum entre deux nombres ordinaires a O (1)

Wikipedia peut aider aussi: http://en.wikipedia.org/wiki/Computational_complexity_theory

La meilleure façon de différencier O (1) et O (n) compare tableau et liste.

Pour tableau, si vous avez le droit valeur d'index, vous pouvez accéder aux données instantanément. (Si vous ne connaissez pas l'index et doivent en boucle à travers le réseau, alors il ne sera pas O (1) plus)

Pour la liste, vous devez toujours faire une boucle à travers elle que vous connaissez l'index ou non.

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

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

Cela signifie que l'accès prend du temps constant à-dire ne dépend pas de la taille de l'ensemble de données. O (n) signifie que l'accès dépend de la taille de l'ensemble de données linéaire.

Le O est également connu comme grand-O.

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

Puisque tout est un degré constant 0 polynomiale, nous pouvons exprimer tout fonction constante Theta (n ^ 0), ou Theta (1). Cette dernière notation est une abus mineurs, cependant, parce qu'il est pas clair quelle variable tend à infini. Nous utiliserons souvent la notation Theta (1) pour désigner soit un constante ou une fonction constante avec relativement à une variable. ... Nous on désigne par O (g (n)) ... l'ensemble de les fonctions f (n) de telle sorte qu'il existe c des constantes positives et n0 de telle sorte que 0 <= f (n) <= c * g (n) pour tout n> = n0. ... A noter que f (n) = Theta (g (n)) implique f (n) = O (g (n)), étant donné que Theta la notation est plus forte que la notation O.

Si un algorithme fonctionne en O (1) le temps, cela signifie que ne asymptotiquement dépend pas de toute variable, ce qui signifie qu'il existe au moins une constante positive que lorsqu'il est multiplié par un est supérieur à la complexité asymptotique (~ exécution) de la fonction pour des valeurs de n supérieures à un certain montant. Techniquement, il est O (n ^ 0) temps.

Voici une simple analogie; Imaginez que vous téléchargez des films en ligne, avec O (1), si cela prend 5 minutes pour télécharger un film, il sera toujours prendre le même temps pour télécharger 20 films. Donc, peu importe combien de films vous téléchargez, ils prendront en même temps (5 minutes) que ce soit un ou 20 films. Un exemple normal de cette analogie est quand vous allez à une bibliothèque de films, si vous prenez un film ou 5, vous tout simplement les prendre à la fois. Par conséquent passer en même temps.

Cependant, avec O (n), si cela prend 5 minutes pour télécharger un film, il faudra environ 50 minutes pour télécharger 10 films. Le temps est donc pas constante ou est en quelque sorte proportionnelle au nombre de films que vous téléchargez.

O (1) un moyen d'accès aléatoire. Dans tous Random Access Memory, le temps nécessaire pour accéder à un élément à un endroit est le même. Ici, le temps peut être tout entier, mais la seule chose à retenir est temps nécessaire pour récupérer l'élément à (n-1) ième ou nième emplacement sera même (c.-à-constant).

considérant O (n) dépend de la taille de n.

Selon mon point de vue,

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

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow