Un anglais simple explication de Big O

Question

Qu'est ce qu'un anglais simple explication de Big O? Avec aussi peu de définition formelle que possible et mathématiques simples.

Answer 1

Il montre comment un algorithme échelles.

O(n²):

• 1 point: 1 seconde
• 10 points: 100 secondes
• 100 objets: 10000 secondes

Remarquez que le nombre d'éléments augmente par un facteur de 10, mais le temps augmente par un facteur de 10^{à 2}. Fondamentalement, n=10 et donc O(n²) nous donne le facteur d'échelle n² 10².

O(n):

• 1 point: 1 seconde
• 10 points: 10 secondes
• 100 objets: 100 secondes

Cette fois, le nombre d'éléments augmente par un facteur de 10, et donc le temps. n=10 et donc O(n) facteur d'échelle est de 10.

O(1):

• 1 point: 1 seconde
• 10 points: 1 seconde
• 100 objets: 1 seconde

Le nombre d'éléments est toujours en augmentation par un facteur de 10, mais le facteur d'échelle de O(1) est toujours de 1.

C'est l'essentiel. Ils réduisent les mathématiques de sorte qu'il peut ne pas être exactement n² ou ce qu'ils disent qu'il est, mais ce sera le facteur dominant dans la mise à l'échelle.

Answer 2

EDIT: remarque, ce n'est presque certainement déroutant Big O la notation (qui est la limite supérieure) avec Theta notation (qui est à la fois supérieure et inférieure). Dans mon expérience, c'est en fait typique de discussions non-universitaire. Toutes mes excuses pour la confusion causée.

En une phrase: Comme la taille de votre travail, combien beaucoup plus de temps faut-il pour le faire?

Évidemment, c'est seulement à l'aide de "taille", comme l'entrée et du "temps" que la sortie — la même idée s'applique si vous voulez parler de l'utilisation de la mémoire etc.

Voici un exemple où on a N T-shirts que nous voulons sèche. Nous allons supposer qu'il est très rapide à mettre dans la position de séchage (c'est à dire l'interaction de l'homme est négligeable). Ce n'est pas le cas dans la vraie vie, bien sûr...

• À l'aide d'une corde à linge à l'extérieur: en supposant que vous avez un infiniment grand jardin, lave-sèche en O(1) fois. Cependant, beaucoup vous avez, vous obtiendrez le même soleil et de l'air frais, de sorte que la taille n'a pas d'incidence sur le temps de séchage.

• À l'aide d'un sèche-linge: vous mettez le 10 chemises à chaque charge, et alors qu'ils ont fait une heure plus tard. (Ignorer les chiffres réels ici — ils sont pas pertinents.) Afin de séchage de 50 chemises prend environ 5 fois plus long que le séchage de 10 chemises.

• Mettre le tout dans un placard d'aération: Si on met le tout dans un gros tas et laisser général de chaleur le faire, il faudra beaucoup de temps pour le moyen-shirts pour vous sécher. Je ne voudrais pas deviner les détails, mais je suppose que c'est au moins O(N^2) — augmentation de la charge de lavage, le temps de séchage augmente plus vite.

Un aspect important de la "big O" de la notation, c'est qu'il ne veut pas dire que l'algorithme sera plus rapide pour une taille donnée. Prendre une table de hachage (clés de la chaîne de valeur entière) vs un tableau de paires (string, integer). Est-il plus rapide de trouver une clé dans la table de hachage ou d'un élément dans le tableau, basé sur une chaîne de caractères? (c'est à dire pour le tableau, "trouver le premier élément sur lequel la partie de chaîne correspond à la clé donnée.") Tables de hachage sont généralement amortis (~= "moyenne") O(1) — une fois qu'ils sont mis en place, il devrait prendre environ le même temps de trouver une entrée dans une inscription de 100 tableau comme dans une 1 000 000 d'entrée de la table. Trouver un élément dans un tableau (basé sur le contenu plutôt que sur l'index) est linéaire, i.e. O(N) en moyenne, vous allez avoir à regarder la moitié des entrées.

Est-ce qu'une table de hachage plus rapide qu'un tableau pour les recherches? Pas nécessairement. Si vous en avez une très petite collection d'entrées, un tableau peut être bien plus rapide — vous pouvez être en mesure de vérifier toutes les chaînes dans le temps qu'il faut pour il suffit de calculer le hashcode de celui que vous êtes en train de regarder. Comme l'ensemble de données grandit, cependant, la table de hachage finalement battre le tableau.

Answer 3

Big O décrit une limite supérieure sur le comportement de la croissance d'une fonction, par exemple l'exécution d'un programme, lorsque les entrées de devenir grand.

Exemples:

• O(n): Si je double la taille de l'exécution des doubles

• O(n²): Si la taille de saisie double la quadruple exécution

• O(log n): Si la taille de saisie en double le moteur d'exécution augmente d'un

• O(2ⁿ): Si la taille de l'image augmente de un, le moteur d'exécution doubles

La taille de saisie est généralement de l'espace de bits nécessaires pour représenter l'entrée.