Qu'est-ce que la notation Big-O? Comment trouvez-vous des chiffres comme O (n)?

Question

Possible en double:
Plain english explanation of Big O

J'imagine que cela est probablement quelque chose enseignée dans les classes, mais comme je un programmeur autodidacte, je ne l'ai vu, il est rare. J'ai compris que c'est quelque chose à voir avec le temps, et O (1) est le meilleur, alors que O (n^n) est très mauvais, mais quelqu'un pourrait-il me donner une explication de base de ce que il représente réellement, et d'où viennent ces chiffres?

Answer 1

Big O se réfère à l'ordre d'exécution le plus défavorable. Il est utilisé pour montrer à quel point un algorithme s'échelonne en fonction de la taille de l'ensemble de données (n-> nombre d'éléments). Puisque nous ne sommes concernés que par la commande, les multiplicateurs constants sont ignorés et tous les termes qui augmentent moins rapidement que le terme dominant sont également supprimés. Quelques exemples:

Une seule opération ou un ensemble d'opérations est O (1), car cela prend un certain temps (ne varie pas en fonction de la taille du jeu de données).

Une boucle est O (n). Chaque élément de l'ensemble de données est bouclé.

Une boucle imbriquée est O (n^2). Une boucle imbriquée imbriquée est O (n^3) et continue. Des choses comme la recherche d'arbre binaire sont log (n), ce qui est plus difficile à montrer, mais à chaque niveau dans l'arbre, le nombre de solutions possibles est divisé par deux, donc le nombre de niveaux est log (n) (fourni l'arbre est équilibré). Quelque chose comme de trouver la somme d'un ensemble de nombres qui est le plus proche d'une valeur donnée est O (n!), Puisque la somme de chaque sous-ensemble doit être calculée. C'est très mauvais.

Answer 2

C'est une façon d'exprimer la complexité du temps. Pour n éléments dans une liste, il faut n calculs pour trier la liste. Ce qui n'est pas mal du tout. Chaque augmentation de n augmente linéairement la complexité temporelle.

O(n^n) est mauvaise, car la quantité de calcul nécessaire pour effectuer un tri (ou quoi que vous fassiez) augmentera exponentiellement à mesure que vous augmentez n.

O(1) est le meilleur, car cela signifie 1 calcul pour effectuer une fonction, pensez à des tables de hachage, la recherche d'une valeur dans une table de hachage a O(1) complexité de temps.

Answer 3

La notation Big O appliquée à un algorithme fait référence à la manière dont le temps d'exécution de l'algorithme dépend de la quantité de données d'entrée. Par exemple, un algorithme de tri prendra plus de temps pour trier un grand ensemble de données qu'un petit ensemble de données. Si, pour l'exemple de l'algorithme de tri, vous représentez graphiquement le temps d'exécution (axe vertical) par rapport au nombre de valeurs à trier (axe horizontal), la nature de la ligne ou de la courbe qui en résulte dépend de l'algorithme de tri utilisé. La notation Big O est une méthode abrégée pour décrire la ligne ou la courbe.

En notation O grande, l'expression entre parenthèses est la fonction qui est représentée graphiquement.Si une variable (disons n) est incluse dans l'expression, cette variable fait référence à la taille de l'ensemble de données d'entrée. Vous dites O (1) est le meilleur. Cela est vrai car le graphe f (n) = 1 ne varie pas avec n. Un algorithme O (1) prend le même temps pour se terminer quelle que soit la taille de l'ensemble de données d'entrée. En revanche, le temps d'exécution d'un algorithme de O (n^n) augmente avec le carré de la taille de l'ensemble de données d'entrée. C'est l'idée de base, pour une explication détaillée, consultez la page wikipedia intitulée «Big O Notation».