que signifie O (N) [dupliquer]

C'est ce qu'on appelle la Notation Big O: http://en.wikipedia.org/wiki/Big_O_notation

Dire que l'insertion est O(n) signifie que vous devez parcourir toute la liste (ou la moitié de celle-ci-la notation big O ignore les facteurs constants) pour effectuer l'insertion.

, Cela ressemble à une belle introduction: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Spécifiquement O (n) signifie que s'il y a 2x autant d'éléments dans la liste, cela prendra pas plus de deux fois plus longtemps, s'il y en a 50 fois plus, ça prendra pas plus de 50 fois plus longtemps. Voir l'article wikipedia que dreeves a souligné pour plus de détails

Edit (en gras ci-dessus): il a été souligné que Big-O représente la limite supérieure, donc s'il y a deux fois plus d'éléments dans la liste, l'insertion prendra à la plupart deux fois plus longtemps, et si il y a 50 fois plus d'éléments, il faudrait à la plupart 50 fois plus longtemps.

Si elle était en outre Ω (N) (Big Omega de n) Alors il faudrait au moins {[2] deux fois plus longtemps pour une liste deux fois plus grande. Si votre implémentation est à la fois O (n) et Ω (n), ce qui signifie qu'elle prendra à la fois à Le moins et à le plus deux fois plus longtemps pour une liste deux fois plus grande, alors on peut dire Qu'Elle Est Θ (N) (Grand thêta de n), ce qui signifie qu'elle prendra exactement comme de nombreux éléments.

Selon Wikipedia (et l'expérience personnelle, en étant coupable moi-même), Big-O est souvent utilisé là où Big-Theta est ce que l'on entend. Il serait techniquement correct d'appeler votre fonction O (n^n^n^n) Car tout ce que Big-O dit, c'est que votre fonction n'est pas plus lente que cela, mais personne ne le dirait autrement que pour prouver un point car ce n'est pas une information très utile et trompeuse, bien qu'elle soit techniquement précise.

O (n) est grande Notation O et fait référence à la complexité d'un algorithme donné. n désigne la taille de l'entrée, dans votre cas, c'est le nombre d'articles dans votre liste.

O(n) signifie que votre algorithme prendra de l'ordre de n opérations pour insérer un élément. par exemple, boucler la liste une fois (ou un nombre constant de fois, comme deux fois ou seulement boucler la moitié).

O(1) signifie qu'il prend un temps constant, qu'il ne dépend pas de combien les éléments sont dans la liste.

O(n^2) signifie que, pour chaque notice, il faut n*n opérations. c'est-à-dire 1 opération pour 1 article, 4 opérations pour 2 articles, 9 opérations pour 3 articles. Comme vous pouvez le voir, les algorithmes O(N^2) deviennent inefficaces pour gérer un grand nombre d'éléments.

Pour les listes O (n) n'est pas mauvais pour l'insertion, mais pas le plus rapide. Notez également que O (n / 2) est considéré comme étant le même que O(n) parce qu'ils croissent tous les deux au même rythme que n.

Il fait référence à la complexité de votre programme, c'est-à-dire au nombre d'opérations nécessaires pour résoudre un problème. O(n) signifie que chaque opération prend le même nombre d'étapes que les éléments de votre liste, qui pour l'insertion, est très lent. De même, si vous avez O (N^2) signifie que toute opération prend "n" nombre carré d'étapes à accomplir, et ainsi de suite... Le "O" est de l'Ordre de Grandeur, et l'expression entre parenthèses est toujours liée au nombre d'éléments manipulés dans le procédure.

Réponse courte: cela signifie que le temps de traitement est en relation linéaire avec la taille de l'entrée. Par exemple, si la taille de l'entrée (Longueur de la liste) Triple, le temps de traitement (à peu près) Triple. Et s'il augmente mille fois, le temps de traitement augmente également de la même ampleur.

Réponse longue: voir les liens fournis par Ian P et dreeves

Cela peut aider:

Http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

O(n): recherche d'un élément dans un liste ou un arbre mal formé (pire des cas); ajout de deux nombres à n chiffres

Bonne chance!

Wikipedia explique beaucoup mieux que je peux, mais cela signifie que si la taille de votre liste est N, il faut au maximum n boucles / itérations pour insérer un élément. (En effet, vous devez itérer sur toute la liste)

Si vous voulez une meilleure compréhension, Il y a un livre gratuit de Berkeley qui va plus en profondeur sur la notation.