Qu'est-ce qu'une explication en anglais simple de la notation « Big O » ?

https://stackoverflow.com/questions/487258

20-08-2019
|

Question

Je préférerais le moins de définition formelle possible et des mathématiques simples.

La solution

Note rapide, ce qui est presque certainement déroutant notation Big O (qui est une limite supérieure) avec notation Theta « Θ » (qui est une borne à deux faces). Dans mon expérience, cela est en fait typique des discussions dans les milieux non universitaires. Toutes mes excuses pour toute confusion causé.

complexité Big O peut être visualisé avec ce graphique:

Analyse Big O

La définition la plus simple que je peux donner pour la notation Big-O est la suivante:

notation Big-O est une représentation relative de la complexité d'un algorithme.

Il y a quelques mots importants et délibérément choisis dans cette phrase:

relative: vous ne pouvez comparer des pommes avec des pommes. Vous ne pouvez pas comparer un algorithme pour faire la multiplication arithmétique à un algorithme qui trie une liste d'entiers. Mais une comparaison de deux algorithmes pour effectuer des opérations arithmétiques (une multiplication, une addition) vous dira quelque chose de significatif;

Représentation: Big-O (dans sa forme la plus simple) réduit la comparaison entre les algorithmes à une seule variable. Cette variable est choisie en fonction des observations ou des hypothèses. Par exemple, les algorithmes de tri sont généralement comparés en fonction des opérations de comparaison (en comparant deux noeuds pour déterminer leur ordre relatif). Cela suppose que la comparaison est cher. Mais si la comparaison ne coûte pas cher, mais est cher swapping? Il change la comparaison; et

complexité: s'il me faut une seconde pour trier 10.000 éléments combien de temps cela me prendra pour trier un million? La complexité de cette instance est une mesure par rapport à autre chose.

Revenez et relire ce qui précède lorsque vous avez lu le reste.

Le meilleur exemple de Big-O je peux penser est faire de l'arithmétique. Prenez deux chiffres (123456 et 789012). Les opérations arithmétiques de base que nous avons apprises à l'école sont:

addition;

soustraction;

multiplication; et

division.

Chacun d'eux est une opération ou un problème. Une méthode de résolution de ces est appelé un algorithme .

L'addition est la plus simple. Vous alignez les numéros vers le haut (à droite) et d'ajouter les chiffres dans une colonne écrit le dernier numéro de cette addition dans le résultat. La partie «des dizaines de de ce nombre est reporté à la colonne suivante.

Supposons que l'ajout de ces chiffres est l'opération la plus coûteuse dans cet algorithme. Il va de soi que d'ajouter ces deux nombres nous devons additionner 6 chiffres (et peut-être porter un 7). Si l'on ajoute deux nombres à 100 chiffres, ensemble, nous devons faire 100 ajouts. Si l'on ajoute deux 10.000 numéros de chiffres nous devons faire 10.000 ajouts.

Voir le modèle? Le complexité (à savoir le nombre d'opérations) est directement proportionnelle au nombre de chiffres n dans le plus grand nombre. Nous appelons O (n) ou complexité linéaire .

Soustraction est similaire (sauf que vous devrez peut-être emprunter au lieu de porter).

est différent de multiplication. Vous alignez les chiffres, prends le premier chiffre du nombre inférieur et multiplier à son tour contre chaque chiffre du nombre supérieur et ainsi de suite chaque chiffre. Donc, pour multiplier nos deux chiffres 6 chiffres que nous devons faire 36 multiplications. Nous devrons peut-être faire autant que 10 ou 11 colonne ajoute pour obtenir le résultat final aussi.

Si nous avons deux nombres de 100 chiffres nous devons faire 10.000 multiplications et 200 ajoute. Pour deux d'un million de numéros de chiffres que nous devons faire un billion (10 ¹²) multiplications et deux millions ajoute.

Comme les échelles de l'algorithme avec n- carré , ceci est O (n ²) ou quadratiquecomplexité . Ceci est un bon moment pour introduire un autre concept important:

Nous ne se soucient que de la partie la plus importante de la complexité.

L'astucieux peut avoir réalisé que nous pourrions exprimer le nombre d'opérations que: n ² + 2n. Mais comme vous l'avez vu de notre exemple avec deux numéros d'un million de chiffres chacun, le second terme (2n) devient insignifiante (représentant 0,0002% du total des opérations à ce stade).

On peut remarquer que nous avons supposé que le scénario du pire cas ici. Tout en multipliant 6 nombres de chiffres si l'un d'eux est à 4 chiffres et l'autre est de 6 chiffres, nous avons seulement 24 multiplications. Cependant, nous calculons le scénario le plus défavorable pour que « n », i.e. lorsque les deux sont 6 chiffres. D'où la notation Big-O est sur le pire scénario d'un algorithme

Le Livre Téléphone

Le meilleur exemple suivant que je peux penser est l'annuaire téléphonique, normalement appelé les pages blanches ou similaire, mais il va varier d'un pays à l'autre. Mais je parle de celui qui énumèrent les gens par nom de famille, puis initiales ou prénom, adresse et éventuellement le numéro de téléphone.

Maintenant, si vous instruisaient un ordinateur pour rechercher le numéro de téléphone pour « John Smith » dans un annuaire téléphonique qui contient 1.000.000 noms, que feriez-vous? Ignorant le fait que vous pouvez deviner dans quelle mesure les S de commencé (supposons que vous ne pouvez pas), que feriez-vous?

Une implémentation typique pourrait être d'ouvrir au milieu, prendre les 500 000 ^e et le comparer à « Smith ». Si elle arrive à être « Smith, John », nous avons juste eu la chance réelle. Beaucoup plus est probable que « John Smith » sera avant ou après ce nom. Si c'est après on divise alors la dernière moitié du livre de téléphone dans la moitié et répéter. Si c'est avant nous divisons la première moitié du livre de téléphone dans la moitié et répéter. Et ainsi de suite.

Ceci est appelé recherche binaire et est utilisé tous les jours dans la programmation que vous le réalisiez ou non.

Donc, si vous voulez trouver un nom dans un annuaire téléphonique d'un million de noms que vous pouvez réellement trouver un nom en faisant cela au plus 20 fois. En comparant les algorithmes de recherche, nous décidons que cette comparaison est notre « n ».

Pour un annuaire téléphonique de 3 noms il faut 2 comparaisons (au plus).

Pour 7, il faut au plus 3.

Pour 15 il faut 4.

...

Pour 1000000 il faut 20.

C'est incroyablement bien est-ce pas?

En termes Big-O est ce O (log n) ou complexité logarithmique . Maintenant, le logarithme en question pourrait être ln (base e), log ₁₀, log ₂ ou une autre base. Peu importe, il est toujours O (log n) comme O (2n ²) et O (100n ²) sont toujours à la fois O (n ²).

Il vaut la peine à ce stade pour expliquer que Big O peut être utilisé pour déterminer trois cas avec un algorithme:

Le meilleur cas: Dans la recherche de l'annuaire téléphonique, le meilleur des cas est que l'on retrouve le nom dans une comparaison. Ceci est O (1) ou complexité constante ;

Cas attendu: Comme indiqué plus haut ceci est O (log n); et

Le pire cas:. Ceci est également O (log n)

Normalement, nous ne nous soucions pas le meilleur des cas. Nous sommes intéressés par l'attendu et le pire des cas. Parfois, l'un ou l'autre d'entre eux seront plus importants.

Retour à l'annuaire téléphonique.

Que faire si vous avez un numéro de téléphone et que vous voulez trouver un nom? La police a un annuaire téléphonique inverse, mais ces look-ups se voient refuser au grand public. Ou sont-ils? Techniquement, vous pouvez recherche inversée un numéro dans un annuaire téléphonique ordinaire. Comment?

Vous commencez au premier nom et de comparer le nombre. Si c'est un match, grand, sinon, vous passez à la suivante. Vous devez le faire de cette façon Becautiliser le répertoire téléphonique est non ordonnée (par numéro de téléphone de toute façon).

Donc, pour trouver un nom donné le numéro de téléphone (recherche inversée):

Le meilleur cas: O (1);

Cas attendu: O (n) (pour 500 000); et

Le pire cas:. O (n) (pour 1000000)

Le Travelling Salesman

Ce problème est assez célèbre dans la science informatique et mérite une mention. Dans ce problème, vous avez des villes N. Chacune de ces villes est liée à 1 ou plusieurs autres villes par une route d'une certaine distance. Le problème du voyageur de commerce est de trouver la plus courte visite qui visite chaque ville.

Cela paraît simple? Détrompez-vous.

Si vous avez 3 villes A, B et C avec des routes entre toutes les paires, vous pouvez aller:

A → B → C

A → C → B

B → C → A

B → A → C

C → A → B

C → B → A

Et bien en fait il y a moins que cela parce que certains d'entre eux sont équivalents (A → B → C et C → B → A sont équivalents, par exemple, parce qu'ils utilisent les mêmes routes, juste en sens inverse).

En réalité il y a 3 possibilités.

Prenez ce 4 villes et vous avez (IIRC) 12 possibilités.

Avec 5 il est 60.

6 devient 360.

Ceci est une fonction d'une opération mathématique appelée factoriel . En gros:

5! = 5 x 4 x 3 x 2 x 1 = 120

6! = 6 x 5 x 4 x 3 x 2 x 1 = 720

7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5040

...

25! = 25 × 24 × ... × 2 × 1 = 15,511,210,043,330,985,984,000,000

...

50! = 50 × 49 × ... × 2 × 1 = 3,04140932 x 10 ⁶⁴

Ainsi, le Big-O du problème Salesman est Travelling O (n!) ou complexité factoriel ou combinatoires .

Au moment où vous obtenez 200 villes il n'y a pas assez de temps dans l'univers pour résoudre le problème avec les ordinateurs traditionnels.

Quelque chose à penser.

polynomiale

Un autre point que je voulais mentionner rapidement que tout algorithme qui a une complexité de O (n ^a) est dit avoir complexité polynomiale ou est résoluble polynomiale .

O (n), O (n ²) etc., sont tous les temps polynomial. Certains problèmes ne peuvent être résolus en temps polynomial. Certaines choses sont utilisées dans le monde à cause de cela. est un excellent exemple. Il est informatiquement difficile de trouver deux facteurs premiers d'un très grand nombre. Si ce n'était pas, nous ne pouvions pas utiliser les systèmes à clé publique que nous utilisons.

Quoi qu'il en soit, que c'est pour mon explication de Big O (espérons plaine anglais) (révisé).

Autres conseils

Il montre comment une échelle de l'algorithme.

O (n ²) : dite complexité quadratique

1 point: 1 seconde
10 articles: 100 secondes
100 éléments: 10000 secondes

Notez que le nombre d'éléments augmente d'un facteur de 10, mais le temps augmente d'un facteur 10 ². Fondamentalement, n = 10 et ainsi de O (n ²) nous donne le facteur d'échelle n ² qui est 10 ².

O (n) : dite complexité linéaire

1 point: 1 seconde
10 produits 10 secondes
100 articles: 100 secondes

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

O (1) : dite complexité Constant

1 point: 1 seconde
10 produits 1 seconde
100 éléments: 1 seconde

Le nombre d'articles ne cesse d'augmenter d'un facteur de 10, mais le facteur d'échelle de O (1) est toujours 1.

O (log n) : connu sous le nom complexité logarithmiques

1 point: 1 seconde
10 produits 2 secondes
100 articles: 3 secondes
1000 produits 4 secondes
10000 produits 5 secondes

Le nombre de calculs n'est augmenté d'un journal de la valeur d'entrée. Donc, dans ce cas, en supposant chaque calcul prend 1 seconde, le journal de l'entrée est le temps n nécessaire, donc log n.

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

notation Big-O (également appelée notation « croissance asymptotique ») est quelles fonctions « ressembles » lorsque vous ignorez les facteurs constants et d'autres choses à l'origine . Nous l'utilisons pour parler de comment échelle chose .

base

pour "suffisamment" de grandes entrées ...

f(x) ∈ O(upperbound) signifie f "croît pas plus vite que" upperbound
f(x) ∈ Ɵ(justlikethis) signifie justlikethis "exactement pousse comme" f(x) ∈ Ω(lowerbound)
lowerbound signifie 9x² "pousse pas plus lent que" 10x²

notation grand-O ne se soucie pas des facteurs constants: la fonction est dit 10x² - x + 2 « croître exactement comme » O(...). Ni ne grand-O asymptotique soins de notation sur les non asymptotique trucs ( « trucs près de l'origine » ou « ce qui se passe quand la taille du problème est faible »): la fonction < => est dit à "croître exactement comme" N*log(N).

Pourquoi voudriez-vous ignorer les parties plus petites de l'équation? Parce qu'ils deviennent complètement éclipsée par les grandes parties de l'équation que vous considérez comme des échelles plus grandes et plus grandes; leur contribution devient éclipsée et hors de propos. (Voir la section exemple).

Autrement dit, il est tout au sujet du rapport que vous allez à l'infini. Si vous divisez le temps réel prend le f(x), vous obtiendrez un facteur constant dans la limite des grandes entrées Intuitivement cela a du sens. « Fonctions échelle comme » un autre si vous pouvez multiplier un pour obtenir l'autre. Autrement dit, quand nous disons ...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... cela signifie que pour le problème "assez grand" tailles N (si on fait abstraction des choses près de l'origine), il existe une constante (par exemple 2,5, complètement composé) tel que:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)

Il y a beaucoup de choix de constante; souvent le « meilleur » choix est connu comme le « facteur constant » de l'algorithme ... mais nous ignorons souvent comme nous ignorons non plus termes (voir la section Facteurs Constant pourquoi ils le font habituellement pas d'importance). Vous pouvez aussi penser à l'équation ci-dessus comme une limite, en disant « Dans le pire scénario, le temps qu'il faut ne sera jamais pire que à peu près N, un facteur de 2,5 (un facteur constant, nous n » SOIGNENT beaucoup sur) ».

En général, est celui Ɵ(N²) plus utile parce que nous nous soucions souvent sur le comportement le plus défavorable. Si représente quelque chose N(N-1)/2 « mauvais » comme le processeur ou l'utilisation de la mémoire, puis « » signifie « N² est le scénario #handshakes ∈ Ɵ(N²) pire cas d'utilisation processeur / mémoire ».

Applications

En tant que construction purement mathématique, la notation grand-O ne se limite pas à parler du temps de traitement et de la mémoire. Vous pouvez l'utiliser pour discuter des asymptote de quoi que ce soit lorsque l'échelle est significatif, par exemple:

le nombre de poignées de main peut-être parmi les personnes à la N*(N-1)/2 partie (order N², en particulier lim, mais ce qui importe est qu'il « cuirasses comme » O(N))
numéro probabiliste prévu de personnes qui ont vu un peu de marketing viral en fonction du temps
comment les échelles de temps de latence de site Web avec le nombre d'unités de traitement dans une unité centrale de traitement ou d'un cluster de GPU ou de l'ordinateur
comment les échelles de sortie de chaleur sur la CPU matrices en fonction du nombre de transistors, la tension, etc.
combien de temps un algorithme a besoin d'exécuter, en fonction de la taille d'entrée
combien d'espace un algorithme a besoin d'exécuter, en fonction de la taille d'entrée

Exemple

Pour l'exemple ci-dessus poignée de main, tout le monde dans une pièce serre la main de tout le monde. Dans cet exemple, O(N log(log(N))). Pourquoi?

Sauvegarder un peu: le nombre de poignées de main est exactement n-choose-2 ou 100000*N log(log(N)) (chacun des N personnes ébranle les mains de N-1 d'autres personnes, mais ce double-counts poignées de main afin de diviser par 2):

href="https://i.stack.imgur.com/rqQMF.png" rel="noreferrer"> adjmatrice acency

Cependant, pour un très grand nombre de personnes, le terme linéaire est éclipsée et + 100*N contribue efficacement 0 au rapport (dans le tableau: la fraction des boîtes vides sur la diagonale sur le total des boîtes devient plus petit que le nombre de participants devient plus grand). Par conséquent, le comportement de mise à l'échelle est O(N!), ou le nombre de poignées de main « pousse comme N² ».

#handshakes(N)
────────────── ≈ 1/2
     N²

Il est comme si les cases vides sur la diagonale du tableau (N * (N-1) / 2 coches) même pas qu'il y avait (N ² coches asymptotiquement).

(digression temporaire « anglais simple » :) Si vous vouliez prouver à vous-même, vous pouvez effectuer une algèbre simple sur le rapport pour le diviser en plusieurs termes ( « moyens considérés O(N log(N)) dans la limite de » , simplement l'ignorer si vous ne l'avez pas vu, il est juste pour la notation « et N est vraiment très grand »):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

tl; dr: Le nombre de de regards comme «poignées de main x² tant pour les grandes valeurs, que si nous devions écrire le rapport # poignées de main / X², le fait que nous ne avons pas besoin exactement x² poignées de main montreraient même pas dans la décimale pour un arbitrairement grand moment.

par exemple. pour x = 1 million, rapport # poignées de main / X²: 0,499999 ...

Immeuble Intuition

Cela nous permet de faire des déclarations comme ...

"Pour assez grand inputsize = N, quel que soit le facteur constant est, si je à double la taille d'entrée ...

... je double le temps d'un O (N) (le "temps linéaire") algorithme prend. »

N → (2N) = 2 ( N )
... je double-carré (quadruple) le temps d'un algorithme O (N²) ( "time quadratique") prend. » (par exemple, un problème aussi grand 100x prend 100² = 10000x aussi longtemps ... peut-être non durable)

N² → (2N) ² = 4 ( N² )
... je double-cubes (octuple), le temps d'un O (N³) ( "time cube") algorithme prend. » (par exemple, un problème aussi grand 100x prend 100³ = 1000000x aussi longtemps ... très non durable)

cN³ → c (2N) ³ = 8 ( cN³ )
... J'ajoute un montant fixe au temps un O (log (N)) ( "heure logarithmique") algorithme prend. » (pas cher!)

c log (N) → log c (2N) = (c log (2)) + ( c log (N) ) = (quantité fixe) + ( c log (N) )
... Je ne change pas le temps d'un O (1) ( "constante de temps") algorithme prend. » (le moins cher!)

c * 1 → c * 1
... I "(en gros) double" le temps d'un O (N log (N)) algorithme prend. » (assez commun)

il est inférieur à O (N ^1,000001), que vous pourriez être prêt à appeler essentiellement linéaire
... J'augmente ridiculement le temps d'un O (2 ^N) ( "temps exponentielle") algorithme prend. » (vous devriez double (ou triple, etc.), temps juste en augmentant le problème par une seule unité)

2 ^N → 2 ^2N = (4 ^N) ......... ... une autre façon ...... mettre 2 ^N → 2 ^{N + 1} = 2 ^N 2 ¹ = 2 2 ^N

[pour le incliné mathématiquement, vous pouvez la souris sur les spoilers pour sidenotes mineurs]

(avec crédit https://stackoverflow.com/a/487292/711085 )

(techniquement le facteur constant pourrait peut-être la matière dans d'autres exemples ésotériques, mais je l'ai formulé les choses ci-dessus (par exemple dans le journal (N)) de telle sorte qu'il ne fonctionne pas)

Ce sont lescommandes du pain et le beurre de croissance que les programmeurs et les informaticiens appliqués utilisent comme points de référence. Ils voient ces tout le temps. (Ainsi, alors que vous pourriez penser techniquement « Doubler l'entrée fait un O (√N) algorithme 1,414 fois plus lent, » il vaut mieux penser comme « cela est pire que logarithmique, mais mieux que linéaire ».)

facteurs constants

En général, nous ne nous soucions pas ce que les facteurs spécifiques sont constants, car ils ne touchent pas la façon dont la fonction se développe. Par exemple, deux algorithmes peuvent aussi bien prendre le temps de remplir O(N²), mais on peut être deux fois plus lent que l'autre. Général, nous ne soucions pas trop à moins que le facteur est très important, étant donné que l'optimisation est affaire délicate ( Quand l'optimisation prématurée ?); aussi le simple fait de choisir un algorithme avec un meilleur grand-O permettra d'améliorer les performances en ordres de grandeur.

Certains algorithmes asymptotiquement supérieurs (par exemple une sorte de non-comparaison O(1)) peut avoir un si grand facteur constant (par exemple), ou O(log(N)) frais généraux relativement importante comme avec un caché x, que O(N^2) ils sont rarement la peine d'utiliser même sur « big data ».

Pourquoi O (N) est parfois le meilleur que vous pouvez faire, à savoir pourquoi nous avons besoin datastructures

O(N)/N algorithmes sont en quelque sorte les algorithmes « meilleurs » si vous avez besoin de lire toutes vos données. acte de lecture un tas de données est une opération O([length of text] + [length of query]). Chargement en mémoire est généralement O(N+M) (ou plus si vous avez un support matériel, ou pas de temps si vous avez déjà lu les données). Toutefois, si vous touchez ou même regarder à chaque élément de données (ou même tous les morceau de données), votre algorithme prendra le temps d'effectuer O([length of text]*[length of query]) cette recherche. Nomatter combien de temps votre algorithme réel prend, il sera au moins parce qu'il a passé O(N*M) que de temps à regarder toutes les données.

La même chose peut être dite pour l'acte d'écriture . Tous les algorithmes qui impriment les choses N prendront le temps N, parce que la sortie est au moins aussi longtemps (par exemple l'impression de toutes les permutations (façons de réorganiser) un ensemble de N cartes à jouer est factoriel: f(x) ∈ O(g(x))).

Ce qui motive l'utilisation de structures de données : une structure de données nécessite la lecture des données qu'une seule fois (généralement le temps |f(x)| ≤ const * |g(x)|), ainsi que une certaine quantité arbitraire de pré-traitement (par exemple, ou O Ω ou o) que nous essayons de garder les petits. Par la suite, la modification de la structure de données (insertions / suppressions / etc.) et de faire des requêtes sur les données prennent très peu de temps, comme ou ω f(x) ∈ Ɵ(g(x)). Vous allez ensuite faire un grand nombre de requêtes! En général, plus le travail que vous êtes prêt à faire à l'avance, moins le travail que vous aurez à faire plus tard.

Par exemple, dites-vous eu les coordonnées de latitude et de longitude de millions de segments de routes, et je voulais trouver toutes les intersections de la rue.

Méthode Naive:. Si vous aviez les coordonnées d'une intersection de la rue, et je voulais examiner les rues avoisinantes, vous devez passer par les millions de segments à chaque fois, et vérifiez chacun pour contiguïté
Si vous ne deviez faire qu'une seule fois, ce ne serait pas un problème d'avoir à faire la méthode naïve du travail qu'une seule fois f(x) ∈ Ω(g(x)), mais si vous voulez le faire plusieurs fois (dans ce cas, const1*g(x) fois, une fois pour chaque segment), nous aurions dû faire le travail const2*g(x) ou 1000000² = 1000000000000 opérations. Pas bon (un ordinateur moderne peut effectuer environ un milliard d'opérations par seconde).
Si nous utilisons une structure simple appelée une table de hachage (une table de consultation vitesse instantanée, aussi connu comme un hashmap ou dictionnaire), nous payons un faible coût par prétraiter tout le temps ==. Par la suite, il ne prend du temps constant en moyenne pour rechercher quelque chose par sa clé (dans ce cas, notre clé est les coordonnées de latitude et de longitude, arrondi dans une grille, on recherche les gridspaces adjacentes dont il n'y a que 9, qui est un constant).
Notre tâche est alléd'un infaisable à un gérable = O(...) ∈ O(...), et tout ce que nous avions à faire était de payer un coût mineur, de faire une table de hachage.
analogie : L'analogie dans ce cas particulier est un puzzle: Nous avons créé une structure de données qui exploite une propriété des données. Si nos segments de route sont des pièces de puzzle comme, nous les regroupons en faisant correspondre la couleur et le motif. Nous exploitons alors cela pour éviter de faire un travail supplémentaire plus tard (en comparant les pièces de puzzle de couleur comme à l'autre, de ne pas tous les une seule pièce de puzzle).

La morale de l'histoire: une structure de données nous permet d'accélérer les opérations. Même plus des structures de données avancées peuvent vous permettre de combiner, de retarder ou même ignorer les opérations de façon incroyablement intelligent. Différents problèmes auraient des analogies différentes, mais ils avaient tous impliquer l'organisation des données d'une manière qui exploite une structure que nous nous soucions, ou que nous avons artificiellement qui lui sont imposées pour la tenue de livres. Nous travaillons à l'avance (planification et organisation essentiellement) et les tâches maintenant répétées sont beaucoup plus facile!

Exemple pratique: visualiser les ordres de croissance tout en codage

notation asymptotique est, à sa base, tout à fait distincte de la programmation. la notation asymptotique est un cadre mathématique pour réfléchir à la façon dont les choses échelle, et peut être utilisé dans de nombreux domaines. Cela dit ... voilà comment vous Appliquer notation asymptotique à coder.

Les bases: Chaque fois que nous interagissons avec tous les éléments dans une collection de taille A (comme un tableau, un ensemble, toutes les clés d'une carte, etc.), ou effectuer une itération d'une boucle, qui est un facteur multiplcative de la taille A. Pourquoi dois-je dire « un facteur multiplicatif » - parce que les boucles et les fonctions (presque par définition) ont multiplicatif temps de fonctionnement: le nombre d'itérations, le temps le travail effectué dans la boucle (ou pour les fonctions: le nombre de fois vous appelez la fonction, les temps travail dans la fonction). (Cela est si nous ne faisons rien de fantaisie, comme des boucles de saut ou de sortir de la boucle au début, ou changer le flux de contrôle dans la fonction basée sur des arguments, ce qui est très commun.) Voici quelques exemples de techniques de visualisation, avec accompagnement pseudocode.

(ici, les unités représentent s ∈ constante de temps de travail, les instructions du processeur, opcodes interprète, quel que soit)

for(i=0; i<A; i++)        // A * ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

Exemple 2:

for every x in listOfSizeA:   // A * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        some O(1) operation       // 1))

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

Exemple 3:

function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

Si nous faisons quelque chose un peu compliqué, vous pourriez encore être en mesure d'imaginer visuellement ce qui se passe:

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

Ici, le contour reconnaissable plus petit, vous pouvez dessiner est ce qui importe; un triangle est une forme tridimensionnelle deux (0,5 A ^ 2), tout comme un carré est une forme à deux dimensions (A ^ 2); le facteur constant de deux ici reste dans le rapport asymptotique entre les deux, mais nous ignorons comme tous les facteurs ... (Il y a quelques nuances malheureuses à cette technique que je ne vais pas développer ici, il peut vous induire en erreur.)

Bien sûr, cela ne signifie pas que les boucles et les fonctions sont mauvaises; au contraire, ce sont les éléments constitutifs des langages de programmation modernes, et nous les aimons. Cependant, nous pouvons voir que la façon dont on tisse des boucles et des fonctions et conditionals avec nos données (flux de contrôle, etc.) imite le temps et l'utilisation de l'espace de notre programme! Si le temps et utilisation de l'espace devient un problème, qui est quand nous avons recours à l'intelligence, et de trouver une structure d'algorithme ou de données facile, nous n'avions pas envisagé, pour réduire l'ordre de croissance en quelque sorte. Néanmoins, ces techniques de visualisation (si elles ne fonctionnent pas toujours) peuvent vous donner une estimation naïve à un pire temps d'exécution.

Voici une autre chose que nous pouvons reconnaître visuellement:

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

Nous pouvons simplement réorganiser cela et voir est O (N):

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

Ou peut-être vous ne vous connectez (N) passe des données, pour le temps total O (N * log (N)):

   <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

Unrelatedly mais vaut la peine de mentionner à nouveau: Si l'on effectue un hachage (par exemple un dictionnaire / Hashtable recherche), qui est un facteur O (1). C'est assez rapide.

[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

Si nous faisons quelque chose de très compliqué, comme avecfonction récursive ou algorithme diviser pour régner, ~~vous pouvez utiliser le (en général travaux), ou dans des cas ridicules du théorème Akra-Bazzi (fonctionne presque toujours)~~ vous regardez le temps d'exécution de votre algorithme sur Wikipedia.

Mais, les programmeurs ne pensent pas comme cela parce que finalement, l'intuition de l'algorithme devient juste une seconde nature. Vous commencerez à code quelque chose inefficace, et tout de suite penser « je suis en train de faire quelque chose totalement inefficace? ». Si la réponse est « oui » et vous le prévoir mattering en fait, vous pouvez prendre un peu de recul et penser à diverses astuces pour faire des choses courir plus vite (la réponse est presque toujours « utiliser une table de hachage », rarement « utiliser un arbre », et très rarement quelque chose d'un peu plus compliqué).

Amorti et la complexité moyenne cas

Il y a aussi le concept de « amorti » et / ou « cas moyen » (notez que ce sont différents).

Case moyenne : Ce n'est pas plus que d'utiliser la notation grand-O pour la valeur attendue d'une fonction, plutôt que la fonction elle-même. Dans le cas habituel où l'on considère toutes les entrées soient tout aussi probable, le cas moyen est juste la moyenne du temps d'exécution. Par exemple avec quicksort, même si le pire cas est pour certaines entrées 2 N² vraiment mauvais, le cas moyen est l'habituel 3 N² (les entrées vraiment mauvaises sont très peu nombreux, si peu que nous ne les remarque pas dans le cas moyenne).

Amorti pire cas : Certaines structures de données peuvent avoir une complexité dans le pire cas qui est importante, mais garantit que si vous faites beaucoup de ces opérations, le montant moyen de travail que vous faites sera mieux que le pire des cas. Par exemple, vous pouvez avoir une structure de données qui prend normalement le temps de constante 1/2 N². Cependant, parfois il sera « hoquet » et prendre le temps pour une 2 N² + log(N) opération aléatoire, parce que peut-être qu'il a besoin de faire une collection de comptabilité ou d'ordures ou quelque chose ... mais il vous promet que si elle ne le hoquet, il ne sera pas le hoquet à nouveau pour N plus d'opérations. Le coût pire cas est encore par opération - N² + N^1.9, mais le coût amorti sur plusieurs pistes est = = par opération Ɵ(...). Parce que les grandes opérations sont suffisamment rares, l'énorme quantité de travail occasionnel peut être considéré comme se fondre dans le reste du travail en tant que facteur constant. Nous disons que le travail est « amorti » sur un nombre suffisamment important d'appels qu'il disparaît asymptotiquement.

L'analogie pour l'analyse après amortissement:

Vous conduisez une voiture. , Vous avez besoin de temps en temps passer 10 minutes va   la station d'essence, puis passer 1 minute remplir le réservoir de gaz.   Si vous avez fait cela à chaque fois que vous êtes allé partout avec votre voiture (passer 10   minutes en voiture de la station d'essence, passer quelques secondes remplir une   fraction d'un gallon), il serait très inefficace. Mais si vous remplissez   le réservoir une fois tous les quelques jours, les 11 minutes consacrées à la conduite à la   station est « amorti » sur un assez grand nombre de voyages,   que vous pouvez l'ignorer et faire semblant tous vos déplacements étaient peut-être 5% plus.

Comparaison entre moyenne et le pire cas amorti:

Moyenne cas: Nous faisons des hypothèses sur nos intrants; à savoir si nos intrants ont des probabilités différentes, nos sorties / runtimes auront des probabilités (que nous prenons la moyenne). Habituellement, nous partons du principe que nos intrants sont tout aussi probable (probabilité uniforme), mais si les entrées réelles ne correspondent pas à nos hypothèses de « entrée moyenne », la production moyenne / calculs d'exécution peut être dénuée de sens. Si vous prévoyez des entrées uniformément au hasard si, ce qui est utile de penser à!
après amortissement le plus défavorable: Si vous utilisez une structure de données le plus défavorable amorti, la performance est garantie d'être dans le pire des cas ... amortis par la suite (même si les entréessont choisis par un mauvais démon qui sait tout et essaie de vous visser plus). Habituellement, nous utilisons pour analyser des algorithmes qui peuvent être très saccadée dans la performance avec de grandes hoquet inattendues, mais au fil du temps exécutons aussi bien que d'autres algorithmes. (Cependant, sauf si votre structure de données a des limites supérieures pour beaucoup de travail exceptionnel, il est prêt à remettre à plus tard sur, un attaquant pourrait le mal peut-être vous forcer à rattraper son retard sur le montant maximum de travail tout à tergiversé une seule fois.

Bien que, si vous êtes raisonnablement inquiets au sujet d'un attaquant, il y a beaucoup d'autres vecteurs d'attaque algorithmiques à se soucier d'ailleurs l'amortissement et le cas moyen.)

Les deux cas la moyenne et l'amortissement sont incroyablement outils utiles pour la réflexion et la conception avec mise à l'échelle à l'esprit.

(voir la différence entre les cas moyen et l'analyse amorti si vous êtes intéressé à ce sous-thème.)

big-O Multidimensional

La plupart du temps, les gens ne se rendent pas compte qu'il ya plus d'une variable au travail. Par exemple, dans un algorithme chaîne de recherche, votre algorithme peut prendre du temps Ɵ(exactlyThis), à savoir qu'il est linéaire dans deux variables comme O(noGreaterThanThis). D'autres algorithmes plus naïfs peuvent être ou <=> <=>. Ignorer plusieurs variables est l'un des oublis les plus courantes que je vois dans l'analyse de l'algorithme, et peut vous handicaper lors de la conception d'un algorithme.

L'histoire

Gardez à l'esprit que grand-O est pas toute l'histoire. Vous pouvez considérablement accélérer certains algorithmes en utilisant la mise en cache, ce qui les rend cache inconscients, ce qui évite les goulots d'étranglement en travaillant avec la RAM au lieu du disque, en utilisant parallélisation, ou faire le travail à l'avance - ces techniques sont souvent indépendant de l'ordre de croissance notation « big-O », bien que vous verrez souvent le nombre de cœurs dans la notation grand-O d'algorithmes parallèles.

Gardez à l'esprit que, en raison des contraintes cachées de votre programme, vous pourriez ne pas vraiment se soucier le comportement asymptotique. Vous pouvez travailler avec un nombre borné de valeurs, par exemple:

Si vous trier quelque chose comme 5 éléments, vous ne voulez pas utiliser le tri rapide de rapide <=>; vous voulez utiliser sorte d'insertion, ce qui arrive à bien performer sur les petites entrées. Ces situations se heurte souvent à des algorithmes diviser pour régner, où vous découpez le problème plus en plus petites, sous-problèmes tels que le tri récursive, transformées de Fourier rapides, ou la multiplication de la matrice.
Si certaines valeurs sont effectivement limitées en raison d'un fait caché (par exemple le nom humain moyen est borné doucement peut-être 40 lettres, et l'âge humain est limitée à voix basse à environ 150). Vous pouvez également imposer des limites sur votre entrée pour rendre efficace les termes constants.

Dans la pratique, même parmi les algorithmes qui ont la même ou similaire la performance asymptotique, leur mérite relatif peut effectivement être conduit par d'autres choses, comme: d'autres facteurs de performance (quicksort et mergesort sont à la fois <=>, mais quicksort profite de caches CPU); considérations non performance, comme la facilité de mise en œuvre; si une bibliothèque est disponible, et comment de bonne réputation et a maintenu la bibliothèque.

Les programmes fonctionneront aussi plus lent sur un ordinateur 500MHz vs ordinateur 2 GHz. Nous ne considérons pas vraiment ce dans le cadre des limites de ressources, parce que nous pensons à l'échelle en termes de ressources de la machine (par exemple par cycle d'horloge), et non par réelle seconde. Cependant, il y a des choses semblables qui peuvent « secrètement » affecter la performance, par exemple si vous utilisez l'émulation, ou si le compilateur de code optimisé ou non. Celles-ci pourraient faire quelques opérations de base prennent plus de temps (même par rapport à l'autre), ou même d'accélérer ou de ralentir certaines opérations asymptotiquement (même par rapport à chaque other). L'effet peut être petite ou grande entre les différentes mise en œuvre et / ou de l'environnement. Avez-vous changez de langue ou de machines à gagner que peu de travail supplémentaire? Cela dépend d'une centaine d'autres raisons (nécessité, compétences, collègues de travail, la productivité du programmeur, la valeur monétaire de votre temps, la familiarité, des solutions de contournement, pourquoi ne pas l'assemblage ou GPU, etc ...), qui peut être plus important que la performance.

Les questions ci-dessus, comme le langage de programmation, ne sont presque jamais considérés comme faisant partie du facteur constant (ils ne devraient pas être); mais il faut être conscient d'entre eux, parce que parfois (bien que rarement) elles peuvent affecter les choses. Par exemple, dans CPython, la mise en œuvre de la file d'attente prioritaire native est asymptotiquement non-optimale (plutôt que <=> pour votre choix <=> d'insertion ou de trouver min); utilisez-vous une autre mise en œuvre? Probablement pas, étant donné que la mise en œuvre de C est probablement plus rapide, et il y a probablement d'autres questions semblables ailleurs. Il y a des compromis; parfois ils importent et parfois ils ne le font pas.

( modifier :. L'explication "anglais simple" se termine ici)

Math addendas

Pour être complet, la définition précise de la notation grand-O est la suivante: que signifie <=> « f est asymptotiquement supérieur borné par const * g »: tout en ignorant ci-dessous une valeur finie de x, il existe une constante de telle sorte que <=>. (Les autres symboles sont les suivants: tout comme signifie ≤ <=>, signifie ≥ Il <=> des variantes minuscules:. et des moyens <=>>.) Signifie à la fois <=> et <=> <=> (supérieure et inférieure délimitée par g): il existe des constantes de telle sorte que f se trouvera toujours dans la « bande » entre <=> et <=>. Il est la déclaration asymptotique plus forte que vous pouvez faire et à peu près équivalent à <=>. (Désolé, j'ai choisi de retarder la mention des symboles de valeur absolue, jusqu'à présent, par souci de clarté,. Surtout parce que je ne l'ai jamais vu des valeurs négatives viennent dans un contexte informatique)

Les gens utilisent souvent <=>, ce qui est peut-être la plus correcte notation 'comp-sci', et tout à fait légitime d'utiliser; « F = O (...) » est lu « f est l'ordre ... / f est délimitée par xxx ... » et est considéré comme « f est une expression asymptotique dont sont ... ». On m'a appris à utiliser le plus rigoureux <=>. <=> signifie « est un élément de » (toujours lire comme précédemment). Est en fait une <=> classe d'équivalence , qui est, il est un ensemble de choses que nous considérons être les mêmes. Dans ce cas particulier, contient des éléments tels que <=> {<=>, <=>, <=>, <=>, <=>, ...} et est infiniment grand, mais il est encore un ensemble. La notation pourrait être <=> une plus commune, et est même utilisé dans les documents par des informaticiens de renommée mondiale. De plus, il est souvent le cas que dans un cadre décontracté, les gens vont dire quand ils veulent dire <=> <=>; cela est techniquement vrai puisque l'ensemble des choses est un sous-ensemble <=> de <=> ... et il est plus facile de taper. ; -)

EDIT: Note rapide, ce qui est presque certainement déroutant notation Big O (qui est une limite supérieure lié) avec la notation Theta (qui est à la fois supérieure et inférieure). Dans mon expérience, c'est en fait typique des discussions dans les milieux non universitaires. Toutes mes excuses pour toute confusion causé.

Dans une phrase: Comme la taille de votre travail monte, combien de temps faut-il pour remplir

Il est évident que c'est seulement en utilisant la « taille » comme entrée et « temps nécessaire » comme 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ù nous avons N T-shirts que nous voulons sécher. Nous allons supposerons il est incroyablement rapide pour les obtenir dans la position de séchage (à savoir l'interaction humaine est négligeable). Ce n'est pas le cas dans la vraie vie, bien sûr ...

En utilisant une ligne de lavage extérieur: en supposant que vous avez une cour arrière infiniment grand, lave sèche en O (1) temps. Cependant que vous avez de lui, il va obtenir le même soleil et l'air frais, de sorte que la taille ne touche pas le temps de séchage.
L'utilisation d'un sèche-linge: vous mettez 10 chemises dans chaque charge, puis ils sont fait une heure plus tard. (Ignorer les chiffres réels ici -. Ils sont hors de propos). Donc, le séchage 50 chemises prend sur les 5 fois plus longtemps que le séchage 10 chemises
Mettre tout dans une armoire de diffusion: Si nous mettons tout en un gros tas et laisser la chaleur générale le faire, il faudra beaucoup de temps pour les chemises moyen pour obtenir sec. Je ne voudrais pas deviner les détails, mais je soupçonne que c'est au moins O (N ^ 2) -. Que vous augmentez la charge de lavage, augmente le temps de séchage plus rapide

Un aspect important de la notation « grand O » est que ne pas dire quel algorithme sera plus rapide pour une taille donnée. Prenez une table de hachage (clé de chaîne, valeur entière) contre un tableau de paires (string, integer). Est-il plus rapide de trouver une clé dans la table de hachage ou un élément du tableau, sur la base d'une chaîne? (Par exemple pour le tableau, « trouver le premier élément dans lequel la partie de chaîne correspond à la clé donnée. ») Hashtables sont généralement amortis (~ = « en moyenne ») O (1) - une fois qu'ils sont mis en place, il devrait prendre environ en même temps pour trouver une entrée dans une table 100 d'entrée comme dans une table d'entrée 1000000. Trouver un élément dans un tableau (basé sur le contenu plutôt que l'indice) est linéaire, à savoir O (N) -. Vous en moyenne, va devoir regarder la moitié des entrées

Est-ce que faire un Hashtable plus vite qu'un tableau pour les recherches? Pas nécessairement. Si vous avez une petite collection d'entrées, un tableau peut bien être plus rapide - vous pouvez être en mesure de vérifier toutes les chaînes dans le temps qu'il faut pour calculer juste le hashcode de celui que vous regardez. Comme l'ensemble de données croît cependant plus grande, la Hashtable finira par battre le tableau.

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 deviennent grandes.

Exemples:

O (n): Si je double la taille d'entrée du double d'exécution
O (n ²): Si la taille d'entrée double le temps d'exécution quadruple
O (log n): Si la taille d'entrée double les augmentations du moteur d'exécution par une
O (2 ⁿ) si la taille d'entrée augmente d'une unité, les doubles d'exécution

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

notation Big O est le plus souvent utilisé par les programmeurs comme une mesure approximative de combien de temps un calcul (algorithme) prendra à complet, exprimée en fonction de la taille de l'ensemble d'entrée.

Big O est utile de comparer comment deux algorithmes vont évoluer à mesure que le nombre d'entrées augmente.

Plus précisément notation Big O est utilisé pour exprimer le comportement asymptotique d'une fonction. Cela signifie que la façon dont la fonction se comporte comme elle tend vers l'infini.

Dans de nombreux cas, le « O » d'un algorithme va tomber dans l'un des cas suivants:

O (1) - Il est temps de terminer est la même quelle que soit la taille de l'entrée réglée. Un exemple accède à un élément de tableau par index.
O (log N) - Temps requis pour remplir l'augmentation à peu près en ligne avec le log2 (n). Par exemple 1024 articles prend à peu près deux fois plus longtemps que 32 articles, parce que log2 (1024) = 10 et log2 (32) = 5. Un exemple est de trouver un élément dans un arbre de recherche binaire (BST).
O (N) - Il est temps de terminer que les échelles de façon linéaire avec la taille de l'ensemble d'entrée. En d'autres termes, si vous doublez le nombre d'éléments dans l'ensemble d'entrée, l'algorithme prend à peu près deux fois plus longtemps. Un exemple est compté le nombre d'éléments dans une liste chaînée.
O (N log N) - Temps pour arriver à compléter par l'augmentation du nombre de fois Articles le résultat de log2 (N). Un exemple de ceci est sorte et Tri rapide .
O (N ^ 2) - Temps pour arriver à compléter est à peu près égal au carré du nombre d'éléments. Un exemple de ceci est bulle sorte.
O (N!) - Il est temps de compléter est le factoriel de l'ensemble d'entrée. Un exemple de ceci est le voyage solution force brute problème de vendeur .

Big O ne tient pas compte des facteurs qui ne contribuent pas d'une manière significative à la courbe de croissance d'une fonction de la taille d'entrée augmente vers l'infini. Cela signifie que les constantes qui sont ajoutés ou multipliés par la fonction sont tout simplement ignorés.

Big O est juste une façon de vous « Express » de manière commune, « Combien de temps / espace-il pour exécuter mon code? ».

Vous pouvez souvent voir O (n), O (n ²), O (nlogn) et ainsi de suite, tout cela ne sont que des façons de montrer; Comment un changement d'algorithme?

O (n) signifie Big O est n, et maintenant vous pourriez penser, "Qu'est-ce que n !?" Eh bien « n » est la quantité d'éléments. L'imagerie que vous voulez rechercher un élément dans un tableau. Vous auriez à regarder chaque élément et comme « Êtes-vous l'élément / élément correct? » dans le pire des cas, l'élément est au dernier indice, ce qui signifie qu'il a fallu autant de temps comme il y a des éléments dans la liste, afin d'être générique, nous disons « oh hey, n est une quantité donnée de juste des valeurs! » .

Alors vous pouvez comprendre ce que « n ² » moyens, mais pour être encore plus précis, jouer avec la pensée que vous avez un simple, le plus simple des algorithmes de tri; bubblesort. Cet algorithme a besoin de regarder à travers la liste, pour chaque élément.

Ma liste

Le flux ici serait:

Comparez 1 et 6, ce qui est le plus grand? Ok 6 est dans la bonne position, aller de l'avant!
Comparer 6 et 3, oh, 3 est moins! Avançons que, Ok la liste a changé, nous devons commencer à partir du début maintenant!

est O n ² parce que, vous avez besoin de regarder tous les éléments de la liste il y a des éléments « n ». Pour chaque élément, vous regardez tous les articles une fois de plus, pour comparer, c'est aussi « n », donc pour chaque article, vous regardez « n » fois ce qui signifie n * n = n ²

J'espère que cela est aussi simple que vous le voulez.

Mais rappelez-vous, Big O est juste une façon de vous experss de la manière du temps et de l'espace.

Big O décrit la nature de mise à l'échelle fondamentale d'un algorithme.

Il y a beaucoup d'informations que Big O ne vous dit pas un algorithme donné. Il coupe à l'os et ne donne que des informations sur la nature de mise à l'échelle d'un algorithme, plus précisément comment l'utilisation des ressources (temps de réflexion ou de la mémoire) d'une échelle de l'algorithme en réponse à la « taille d'entrée ».

Considérons la différence entre un moteur à vapeur et une fusée. Ils ne sont pas seulement différentes variétés de la même chose (comme, par exemple, un moteur Prius par rapport à un moteur Lamborghini), mais ils sont très différents types de systèmes de propulsion, à leur base. Un moteur à vapeur peut être plus rapide qu'une fusée jouet, mais pas de moteur à piston à vapeur sera en mesure d'atteindre les vitesses d'un véhicule de lancement orbital. En effet, ces systèmes ont des caractéristiques de mise à l'échelle en ce qui concerne la relation de carburant nécessaire ( « l'utilisation des ressources ») pour atteindre une vitesse donnée ( « taille d'entrée »).

Pourquoi est-ce si important? Parce que logiciel traite des problèmes qui peuvent varier en taille par des facteurs jusqu'à un billion de dollars. Considérez que pour un moment. Le rapport entre la vitesse nécessaire pour se rendre à la vitesse de marche Lune et humaine est inférieure à 10 000: 1, et qui est absolument minuscule par rapport à la plage en entrée tailles logiciel peut faire face. Et parce que le logiciel peut faire face à une plage astronomique en entrée tailles il est possible de la complexité Big O d'un algorithme, il est dans la nature de l'échelle fondamentale, pour l'emporter sur tous les détails de mise en œuvre.

Prenons l'exemple de tri canonique. Tri Bubble est O (n ²) en fusion-tri est O (n log n). Disons que vous avez deux applications de tri, l'application A qui utilise bulle tri et de l'application B qui utilise fusionner tri, et disons que pour les tailles d'entrée d'environ 30 éléments A l'application est plus rapide que l'application 1000 X B au tri. Si vous ne devez trier beaucoup plus de 30 éléments, alors il est évident que vous préférez l'application A, car il est beaucoup plus rapide à ces tailles d'entrée. Cependant, si vous constatez que vous pourriez avoir à trier dix millions d'articles, alors ce que vous attendez est que l'application B se termine effectivement par être des milliers de fois plus rapide que l'application A dans ce cas, tout à fait en raison de la façon dont chacun des échelles de l'algorithme.

Voici le bestiaire anglais simple j'ai tendance à utiliser pour expliquer les variétés communes de Big-O

Dans tous les cas, préfèrent des algorithmes plus haut sur la liste à ceux plus bas sur la liste. Cependant, le coût du passage à une classe de complexité plus cher varie considérablement.

O (1):

Pas de croissance. Peu importe la taille que le problème est, vous pouvez le résoudre dans le même laps de temps. Ceci est quelque peu analogue à la radiodiffusion où elle prend la même quantité d'énergie à diffuser sur une distance donnée, quel que soit le nombre de personnes qui se trouvent dans la zone de diffusion.

O (log n ):

Cette complexité est le même que O (1) sauf qu'il est juste un peu pire. Pour toutes fins pratiques, vous pouvez considérer cela comme une très grande échelle constante. La différence de travail entre le traitement 1 mille et 1 milliard articles est seulement un facteur six.

O ( n ):

Le coût de la résolution du problème est proportionnel à la taille du problème. Si votre problème double de la taille, le coût de la solution double. Étant donné que la plupart des problèmes doivent être scannés dans l'ordinateur d'une certaine façon, comme la saisie des données, lit disque ou le trafic réseau, ce qui est généralement un facteur d'échelle abordable.

O ( n log n ):

Cette complexité est très similaire à O ( n ) . À toutes fins pratiques, les deux sont équivalents. Ce niveau de complexité serait généralement considéré comme toujours évolutive. Par hypothèses peaufinage certains O ( n log n ) algorithmes peuvent être transformés en O ( n ) algorithmes . Par exemple, limitant la taille des clés réduit le tri de O ( n log n ) O ( n ) .

O ( n ²):

croît comme un carré, où n est la longueur du côté du carré. C'est le même taux de croissance que « l'effet réseau », où tout le monde dans un réseau peut connaître tout le monde dans le réseau. La croissance est cher. La plupart des solutions évolutives ne peuvent pas utiliser des algorithmes avec ce niveau de complexité sans faire de la gymnastique significative. Cela vaut généralement à toutes les autres complexités polynomiale - O ( n ^k) -. Et

O (2 ⁿ):

Ne pas l'échelle. Vous avez sans espoir de résoudre un problème non trivialement taille. Utile pour savoir ce qu'il faut éviter, et des experts pour trouver des algorithmes qui sont approximatives O ( n ^k) .

Big O est une mesure de combien de temps / espace un algorithme utilise par rapport à la taille de son entrée.

Si un algorithme est O (n), le temps / espace augmentera au même rythme que son entrée.

Si un algorithme est O (n ²), alors le temps / augmentation de l'espace à la vitesse de son entrée au carré.

et ainsi de suite.

Il est très difficile de mesurer la vitesse des programmes logiciels, et quand nous essayons, les réponses peuvent être très complexes et rempli d'exceptions et cas particuliers. Ceci est un gros problème, parce que toutes ces exceptions et cas particuliers sont source de distraction et inutile quand on veut comparer deux programmes différents entre eux pour savoir qui est « le plus rapide ».

En raison de cette complexité inutile, les gens essaient de décrire la vitesse des programmes logiciels en utilisant les expressions complexes les plus petits et les moins (mathématiques) possible. Ces expressions sont des approximations très grossières. Bien que, avec un peu de chance, ils captureront l ' « essence » de savoir si un logiciel est rapide ou lent

Parce qu'ils sont des approximations, nous utilisons la lettre « O » (Big Oh) dans l'expression, comme une convention pour signaler au lecteur que nous faisons une schématisation grossière. (Et pour faire en sorte que personne ne pense à tort que l'expression est de toute façon précise).

Si vous lisez le « Oh » comme signifiant « l'ordre de » ou « approximativement », vous ne serez pas aller trop loin mal. (Je pense que le choix du Big Oh aurait pu être une tentative d'humour).

La seule chose que ces expressions « Big-Oh » essayer de faire est de décrire à quel point le logiciel ralentit à mesure que nous augmentons la quantité de données que le logiciel doit traiter. Si on double la quantité de données qui doit être traitée, le logiciel ne doit deux fois plus de temps pour terminer son travail? Dix fois plus longtemps? Dans la pratique, il y a un nombre très limité de grands-Oh expressions que vous rencontrerez et besoin de s'inquiéter:

Le bon:

O(1) constante . Le programme prend en même temps pour courir, peu importe la taille de l'entrée est
O(log n) logarithmiques . Le programme d'exécution augmente lentement, même avec de fortes augmentations de la taille de l'entrée

La mauvaise:

O(n) Linear :. Le programme d'exécution augmente proportionnellement à la taille de l'entrée
O(n^k) polynomiale : -. Le temps de traitement croît plus rapidement et plus rapide - en fonction polynomiale - que la taille de l'entrée augmente

... et le laid:

O(k^n) Exponentielle Le programme gestion de temps augmente très rapidement avec une augmentation même modérée de la taille du problème -. Il est pratique pour traiter de petits ensembles de données avec des algorithmes exponentiels
O(n!) factoriel Le programme d'exécution sera plus long que vous pouvez vous permettre d'attendre quoi que ce soit, mais les jeux de données très petits et les plus trivial-semblants.

Qu'est-ce qu'une explication anglaise plaine de Big O? Avec aussi peu de définition formelle que les mathématiques possible et simple.

Plain English Explication du Besoin pour la notation Big-O:

Quand on programme, nous essayons de résoudre un problème. Ce que nous code est appelé un algorithme. notation Big O nous permet de comparer les moins bonnes performances de cas de nos algorithmes de manière standardisée. spécifications matérielles varient au fil du temps et des améliorations dans le matériel peuvent réduire le temps qu'il faut un algorithme pour exécuter. Mais en remplaçant le matériel ne signifie pas que notre algorithme est mieux ou amélioré au fil du temps, notre algorithme est toujours le même. Ainsi, afin de nous permettre de comparer les différents algorithmes, afin de déterminer si l'on est mieux ou non, nous utilisons la notation Big O.

Plain English Explication de Qu'est-ce que Big O notation est:

ne sont pas tous les algorithmes fonctionnent dans le même laps de temps, et peuvent varier en fonction du nombre d'éléments dans l'entrée, que nous appellerons n . Sur cette base, nous considérons l'analyse pire des cas, ou une limite supérieure de l'exécution comme n plus en plus grands. Nous devons être conscients de ce que n est, parce que beaucoup des notations Big O y faire référence.

Une réponse simple et directe peut être:

Big O représente le pire moment possible / espace pour cet algorithme. L'algorithme ne sera jamais prendre plus d'espace / temps au-dessus de cette limite. Big O représente la complexité du temps / espace dans le cas extrême.

Ok, mes 2cents.

Big-O, est taux de croissance des ressources consommées par le programme, w.r.t. problème instance taille

Ressources: Peut-être le temps total CPU, pourrait être l'espace de RAM au maximum. Par défaut fait référence au temps CPU.

Supposons que le problème est "Trouver la somme",

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

problème instance = {5,10,15} ==> problème instance-size = 3, itérations en boucle = 3

problème instance = {} 5,10,15,20,25 ==> problème instance-size = 5 itérations en boucle = 5

Pour l'entrée de la taille « n » le programme se développe à une vitesse d'itérations « n » dans la matrice. Par conséquent Big-O est exprimé en N O (n)

Supposons que le problème est "trouver la combinaison",

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

problème instance = {5,10,15} ==> problème instance-size = 3, Total itérations = 3 * 3 = 9

problème instance = {} 5,10,15,20,25 ==> problème instance-size = 5, Total itérations = 5 * 5 = 25

Pour l'entrée de la taille « n » le programme se développe à une vitesse d'itérations « n * n » en tableau. Par conséquent Big-O est N ² exprimée en O (n ²)

notation Big O est une façon de décrire la limite supérieure d'un algorithme en termes d'espace ou de temps en cours d'exécution. Le n est le nombre d'éléments du problème (i.e. taille d'un tableau, le nombre de noeuds dans un arbre, etc.) Nous sommes intéressés à décrire le temps d'exécution en tant que n devient grand.

Quand nous disons un algorithme est O (f (n)), nous disons que le temps d'exécution (ou l'espace nécessaire) par cet algorithme est toujours inférieure à une constante fois f (n).

Dire que la recherche binaire a une durée de O (log n) est-à-dire qu'il existe une constante c que vous pouvez multiplier log (n) par qui sera toujours plus grande que la durée de la recherche binaire. Dans ce cas, vous aurez toujours un facteur constant de comparaisons de log (n).

En d'autres termes où g (n) est la durée de votre algorithme, on dit que g (n) = O (f (n)) lorsque g (n) <= c * f (n) lorsque n> k, où k et c sont des constantes.

" Qu'est-ce qu'une explication anglaise plaine de Big O? Avec aussi peu formelle définition que les mathématiques possible et simple. "

Une telle question magnifiquement simple et court semble au moins pour mériter une réponse aussi courte, comme un étudiant peut recevoir au cours du tutorat.

notation Big O indique simplement combien de temps * un algorithme peut fonctionner à l'intérieur, en termes de uniquement la quantité de données d'entrée **.

(* dans un merveilleux, sans unité sens du temps!)
(** qui est ce qui compte, parce que les gens toujours veulent plus , qu'ils vivent aujourd'hui ou demain)

Eh bien, ce qui est si merveilleux sur la notation Big O si c'est ce qu'il fait?

En pratique, l'analyse Big O est si utile et important parce que Big O met ainsi l'accent sur l'algorithme propre complexité et complètement ignore tout ce qui est simplement un moteur de proportionnalité comme constante un JavaScript, la vitesse d'une unité centrale de traitement, votre connexion Internet, et toutes ces choses qui deviennent deviennent rapidement risiblement pas à jour comme modèle T . Big O se concentre sur la performance que de la manière qui compte également autant aux personnes vivant dans le présent ou dans le futur.
notation Big O brille également un coup de projecteur directement sur le principe le plus important de la programmation informatique / ingénierie, le fait qui inspire tous les bons programmeurs de continuer à penser et à rêver: la seule façon d'obtenir des résultats au-delà de la mars au ralenti avant de la technologie est de inventer un meilleur algorithme .

Exemple d'algorithme (Java) :

// given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}

Description de l'algorithme :

Cet algorithme parcourt une liste, élément par élément, à la recherche d'une clé,
Itérer sur chaque élément de la liste, si c'est la clé, retournez True,
Si la boucle s'est terminée sans trouver la clé, renvoyez False.

La notation Big-O représente la limite supérieure de la complexité (temps, espace, ..)

Pour trouver The Big-O sur Time Complexity :

Calculez combien de temps (en fonction de la taille d'entrée) prend le pire des cas :
Pire cas:la clé n'existe pas dans la liste.
Temps (pire des cas) = 4n+1
Temps:O (4n + 1) = o (n) | Dans Big-O, les constantes sont négligées
O(n) ~ Linéaire

Il existe également Big-Omega, qui représente la complexité du Best-Case :

Meilleur cas:la clé est le premier élément.
Temps (meilleur des cas) = 4
Temps:Ω(4) = O(1) ~ Instantané\Constante

Big O

f (x) = O ( g (x)) où x va à un (par exemple, a = + ∞) signifie qu'il existe une fonction < em> k tel que:

f (x) = k (x) g (x)
k est bornée dans un voisinage d'un (si = + ∞, cela signifie qu'il ya des nombres N et M tel que pour tout x> N, | k (x) |

En d'autres termes, en anglais simple: f (x) = O ( g (x)), x → a, signifie que dans un voisinage d'un, f se décompose en le produit de g et une fonction limitée.

Petit o

Par ailleurs, voici à titre de comparaison la définition des petites o.

f (x) = o ( g (x)) où x va à un signifie qu'il y a une fonction k tel que:

f (x) = k (x) g (x)
k (x) tend vers 0 lorsque x tend vers a.

Exemples

sin x = O (x) lorsque x → 0.
sin x = O (1) lorsque x → + ∞,
x ² + x = O (x) lorsque x → 0,
x ² + x = O (x ²) lorsque x → + ∞,
ln (x) = o (x) = O (x) lorsque x → + ∞.

Attention La notation avec le signe égal "=" utilise une "égalité faux": il est vrai que o (g (x)) = O (g (x)), mais faux que O (g (x)) = o (g (x)). De même, il est autorisé à écrire "ln (x) = o (x) lorsque x → + ∞", mais la formule "o (x) = ln (x)" aurait pas de sens.

Autres exemples

O (1) = O (n) = O (n ²) lorsque n → + ∞ (mais pas l'inverse, l'égalité est "faux"),
O (n) + O (n ²) = O (n ²) lorsque n → + ∞
O (O (n ²)) = O (n ²) lorsque n → + ∞
O (n ²) O (n ³) = O (n ⁵) lorsque n → + ∞

Voici l'article de Wikipedia: https://en.wikipedia.org/wiki/Big_O_notation

notation Big O est une façon de décrire la rapidité avec laquelle un algorithme courrons donné un nombre arbitraire de paramètres d'entrée, que nous appellerons « n ». Il est utile dans la science informatique, car différentes machines fonctionnent à des vitesses différentes, et simplement dire qu'un algorithme prend 5 secondes ne vous dit pas grand-chose parce que pendant que vous pouvez exécuter un système avec un 4,5 Ghz processeur octo-core, je courrai un ancien système, 800 mégahertz de 15 ans, ce qui pourrait prendre plus de temps, peu importe l'algorithme. Ainsi, au lieu de spécifier à quelle vitesse un algorithme court en termes de temps, nous disons à quelle vitesse il fonctionne en termes de nombre de paramètres d'entrée, ou « n ». En décrivant les algorithmes de cette façon, nous sommes en mesure de comparer les vitesses d'algorithmes sans avoir à prendre en compte la vitesse de l'ordinateur lui-même.

Je ne sais pas je contribue encore à ce sujet, mais encore pensé que je partage: J'ai trouvé une fois ce blog pour avoir des explications très utiles (bien que très basique) et des exemples sur Big O:

Par exemple, cela a permis d'obtenir les bases nues dans mon crâne écaille de tortue comme, donc je pense que c'est une jolie descente de 10 minutes lire pour vous aider à dirigiez dans la bonne direction.

Vous voulez savoir tout ce qu'il ya à connaître de grand O? Donc, dois-je.

Donc, pour parler de grand O, je vais utiliser des mots qui ont un seul battement en eux. Un son par mot. Les petits mots sont rapides. Vous connaissez ces mots, et moi aussi, nous allons utiliser des mots avec un son. Ils sont petits. Je suis sûr que vous saurez tous les mots que nous utiliserons!

Maintenant, vous et moi de parler du travail. La plupart du temps, je n'aime pas le travail. Est-ce que vous aimez le travail? Il peut être le cas que vous faites, mais je suis sûr que je ne le fais pas.

Je ne veux pas aller au travail. Je n'aime pas à passer du temps au travail. Si je devais mon chemin, je voudrais juste jouer et faire des choses amusantes. Vous sentez-vous la même chose que moi?

Maintenant parfois, je dois aller travailler. Il est triste, mais vrai. Donc, quand je suis au travail, j'ai une règle: j'essaie de faire moins de travail. Comme près de pas de travail que je peux. Ensuite, je vais jouer!

Alors, voici les grandes nouvelles: le grand O peut me aider à ne pas faire le travail! Je peux jouer plus de temps, si je sais grand O. Moins de travail, plus de jeu! C'est ce grand O me aide à faire.

Maintenant, j'ai du travail. J'ai cette liste: un, deux, trois, quatre, cinq, six. Je dois ajouter toutes choses dans cette liste.

Wow, je déteste le travail. Mais oh bien, je dois le faire. Donc, ici je vais.

Un plus deux est trois ... plus trois six ... et quatre est ... Je ne sais pas. Je me suis perdu. Il est trop difficile pour moi de le faire dans ma tête. Je ne aime pas beaucoup pour ce genre de travail.

Alors il ne faut pas faire le travail. Laissez vous et moi penser à quel point il est difficile. Quelle quantité de travail que je dois faire, d'ajouter six chiffres?

Eh bien, nous allons voir. Je dois ajouter un et deux, puis l'ajouter à trois, puis l'ajouter à quatre ... Dans l'ensemble, je compte six ajoute. Je dois faire six ajoute à résoudre ce problème.

vient ici grand O, pour nous dire à quel point dur ce calcul est.

Big O dit: nous devons faire six ajoute à résoudre ce problème. Un ajouter, pour chaque chose de un à six. Six petits morceaux de travail ... chaque bit de travail est un add.

Eh bien, je ne vais pas faire le travail pour les ajouter maintenant. Mais je sais comment il serait difficile. Il serait six ajoute.

Oh non, maintenant j'ai plus de travail. Sheesh. Qui fait ce genre de choses!

Maintenant, ils me demandent d'ajouter de un à dix! Pourquoi devrais-je le faire? Je ne voulais pas ajouter un à six. Pour ajouter de un à dix ... eh bien ... ce serait encore plus dur!

Combien serait-il difficile? Combien plus de travail que je dois faire? Ai-je besoin plus ou moins d'étapes?

Eh bien, je suppose que je devrais faire dix ajoute ... une pour chaque chose d'un à dix. Dix est plus de six. Je dois travailler beaucoup plus à ajouter de un à dix, d'un à six!

Je ne veux pas ajouter en ce moment. Je veux juste penser à quel point il pourrait être d'ajouter que beaucoup. Et, je l'espère, de jouer le plus tôt possible.

Pour ajouter un à six, qui est un travail. Mais voyez-vous, d'ajouter de un à dix, qui est plus de travail?

Big O est votre ami et le mien. Big O nous aide à réfléchir sur la quantité de travail que nous devons faire, afin que nous puissions planifier. Et, si nous sommes amis avec grand O, il peut nous aider à choisir le travail qui est pas si dur!

Maintenant, nous devons faire de nouveaux travaux. Oh non. Je n'aime pas cette chose de travail du tout.

Le nouveau travail: ajouter toutes les choses d'un à n

Attendez! Qu'est-ce que n? Est-ce que cela me manque? Comment puis-je ajouter un à n si vous ne me dites pas ce que n est?

Eh bien, je ne sais pas ce que n est. Je n'ai pas dit. Avez-vous été? Non? Tant pis. Donc, nous ne pouvons pas faire le travail. Ouf.

Mais si nous ne le ferons pas le travail maintenant, on peut deviner à quel point il serait, si nous savions n. Il faudrait ajouter des choses n, non? Bien sûr!

Maintenant vient ici grand O, et il nous dira comment ce travail est difficile. Il dit: pour ajouter toutes les choses d'un à N, un par un, est O (n). Pour ajouter toutes ces choses, [je sais que je dois ajouter n fois.] [1] C'est grand O! Il nous raconte comment il est difficile de faire un certain type de travail.

Pour moi, je pense à grand O comme un grand, lent, l'homme de patron. Il pense que le travail, mais il ne le fait pas. Il pourrait dire: « Ttravail chapeau est rapide. » Ou, il pourrait dire: « Ce travail est si lent et dur! » Mais il ne fait pas le travail. Il a l'air juste au travail, puis il nous dit combien de temps cela pourrait prendre.

Je me soucie beaucoup de gros O. Pourquoi? Je n'aime pas travailler! Personne n'aime travailler. Voilà pourquoi nous aimons tous les grands O! Il nous dit à quelle vitesse nous pouvons travailler. Il nous aide à penser à la façon dont le travail est.

Uh oh, plus de travail. Maintenant, il ne faut pas faire le travail. Mais, nous allons faire un plan pour le faire, étape par étape.

Ils nous ont donné un jeu de dix cartes. Ils sont tous mélangés: sept, quatre, deux, six ... pas droit du tout. Et maintenant ... notre travail consiste à les trier.

Ergh. Cela ressemble à beaucoup de travail!

Comment peut-on régler cette plate-forme? J'ai un plan.

Je vais regarder chaque paire de cartes, paire par paire, à travers la plate-forme, du premier au dernier. Si la première carte dans une paire est grande et la carte suivante dans cette paire est petite, je les échanger. Sinon, je vais à la paire suivante, et ainsi de suite et ainsi de suite ... et bientôt, le pont est fait.

Quand le pont est fait, je demande: ai-je échanger des cartes dans ce passe? Si oui, je dois tout faire une fois de plus, à partir du haut.

À un moment donné, à un moment donné, il n'y aura pas de swaps et notre genre de la plate-forme serait fait. Donc, beaucoup de travail!

Eh bien, combien de travail serait-ce, pour trier les cartes avec ces règles?

J'ai dix cartes. Et, la plupart du temps - qui est, si je n'ai pas beaucoup de chance -. Je dois traverser tout le pont jusqu'à dix fois, jusqu'à dix swaps de carte à chaque fois par la plate-forme

Big O, aidez-moi!

Big O arrive et dit:. Pour un jeu de cartes n, pour trier cette façon se fera en O (N carré) Temps

Pourquoi dit-il n au carré?

Eh bien, vous savez n Squared est n fois n. Maintenant, je comprends: n cartes vérifié, jusqu'à ce qui pourrait être n fois à travers le pont. C'est deux boucles, chacune avec n étapes. C'est n beaucoup de travail à faire au carré. Beaucoup de travail, bien sûr!

Maintenant, quand grand O dit qu'il faudra O (n carré) travail, il ne veut pas dire n au carré ajoute, sur le nez. Il est peut-être un petit peu moins, pour certains cas. Mais dans le pire des cas, il sera près n carré étapes de travail pour trier la plate-forme.

Maintenant, voici où grand O est notre ami.

Big O signale ceci: comme n obtient grand, quand on trie les cartes, le travail est BEAUCOUP PLUS DUR que l'ancien juste add-ces-choses travail. Comment savons-nous cela?

Eh bien, si n devient vraiment grand, nous ne nous soucions pas ce que nous pourrions ajouter à n ou n au carré.

Pour grand n, n carré est plus grand que n.

Big O nous dit que pour arranger les choses est plus difficile que d'ajouter des choses. O (n au carré) est plus O (n) pour le grand n. Cela signifie que:. Si n devient vraiment grand, pour trier une plate-forme mixte de choses n doit prendre plus de temps, que de simplement ajouter n choses mixtes

Big O ne résout pas le travail pour nous. Big O nous dit à quel point le travail est.

J'ai un paquet de cartes. Je l'ai fait les trier. Vous avez aidé. Merci.

Y at-il un moyen plus rapide pour trier les cartes? O grand peut-il nous aider?

Oui, il y a une façon plus rapide! Il faut un certain temps pour apprendre, mais ça fonctionne ... et cela fonctionne assez vite. Vous pouvez aussi, mais prenez votre temps à chaque étape et ne perdez pas votre place.

Dans cette nouvelle façon de trier une plate-forme, nous ne vérifions pas les paires de cartes comme nous l'avons fait il y a un certain temps. Voici vos nouvelles règles pour trier cette plate-forme:

Un: je choisis une carte dans la partie de la plate-forme que nous travaillons maintenant. Vous pouvez choisir un pour moi si vous le souhaitez. (La première fois que nous faisons cela, « la partie de la plate-forme que nous travaillons maintenant » est la plate-forme tout, bien sûr.)

Deux: J'évasement la plate-forme sur cette carte que vous avez choisi. Quel est ce évasement; comment puis-je évasement? Eh bien, je vais de la carte de départ vers le bas, un par un, et je cherche une carte qui est plus élevé que la carte évasement.

Trois: Je vais de la carte fin, et je cherche une carte qui est plus bas que la carte évasement.

Une fois que je l'ai trouvé ces deux cartes, je les échanger, et continuer à chercher d'autres cartes à échanger.Autrement dit, je reviens à la deuxième étape, et évasement sur la carte que vous avez choisi un peu plus.

À un certain moment, cette boucle (de deux à trois) prendra fin. Elle se termine lorsque les deux moitiés de cette recherche se rencontrent à la carte évasement. Ensuite, nous avons juste évasé la plate-forme avec la carte que vous avez choisi dans la première étape. Maintenant, toutes les cartes à proximité du départ sont plus bas que la carte évasement; et les cartes vers la fin sont plus élevés que la carte évasement. truc cool!

Quatre (ce qui est la partie amusante): J'ai deux petits ponts maintenant, un plus bas que la carte évasement, et un plus élevé. Maintenant, je vais à la première étape, sur chaque petit pont! C'est-à-dire, je commence de la première étape sur le premier petit pont, et quand ce travail est fait, je commence de la première étape sur le prochain petit pont.

Je briser le pont en pièces et trier chaque partie, plus petite et plus petite, et à un moment je n'ai pas plus de travail à faire. Maintenant, cela peut sembler lent, avec toutes les règles. Mais croyez-moi, il ne tarde pas du tout. Il est beaucoup moins de travail que la première façon de trier les choses!

Qu'est-ce que ce genre appelé? Il est appelé rapide Trier! Ce genre a été faite par un homme appelé C. A. R. Hoare et il l'a appelé rapide Trier. Maintenant, tri rapide se habitue tout le temps!

Trier rapide casse grands ponts en petits. C'est-à-dire, il se brise de grandes tâches dans les petites.

Hmmm. Il peut y avoir une règle là-bas, je pense. Pour faire de grandes petites tâches, les briser.

Ce genre est assez rapide. À quelle vitesse? Big O nous dit: ce type a besoin O (n log n) travail à faire, dans le cas moyen.

est-il plus ou moins vite que la première sorte? Big O, s'il vous plaît aider!

Le premier tri est O (n au carré). Mais est rapide Trier O (n log n). Vous savez que n log n est inférieur à n au carré, pour le grand n, non? Eh bien, voilà comment nous savons que rapide Trier est rapide!

Si vous devez trier une plate-forme, ce qui est la meilleure façon? Eh bien, vous pouvez faire ce que vous voulez, mais je choisirais Tri rapide.

Pourquoi dois-je choisir Trier rapide? Je n'aime pas travailler, bien sûr! Je veux faire le travail dès que je peux le faire.

Comment puis-je savoir Trier rapide est moins de travail? Je sais que O (n log n) est inférieure à O (n au carré). L'O de sont plus petits, si rapide Trier moins de travail!

Maintenant, vous connaissez mon ami, Big O. Il nous aide à faire moins de travail. Et si vous connaissez grand O, vous pouvez le faire moins de travail aussi!

Vous avez appris tout cela avec moi! Tu es tellement intelligent! Merci beaucoup!

Maintenant que le travail est fait, allons jouer!

[1]: Il existe un moyen de tricher et d'ajouter toutes les choses d'un à n, en une seule fois. Un gamin nommé Gauss l'a découvert quand il avait huit ans. Je ne suis pas intelligent, donc ne me demandez pas comment il l'a fait .

Supposons que nous parlons d'un algorithme , qui devrait faire quelque chose avec un ensemble de données de taille n .

Ensuite moyens O( <some expression X involving n> ), en anglais simple:

Si vous êtes malchanceux lors de l'exécution A, il peut prendre des opérations X (n) complète.

Comme il arrive, il y a certaines fonctions (penser à eux comme implémentations X (n) ) qui ont tendance à se produire assez souvent. Ceux-ci sont bien connus et facilement comparés (Exemples: 1 Log N, N, N^2, N!, etc ..)

En comparant ces quand on parle de et d'autres algorithmes, il est facile de classer les algorithmes en fonction du nombre d'opérations qu'ils peut (pire cas) exiger Achevée.

En général, notre objectif sera de trouver ou de structurer un algorithme de telle sorte qu'il aura une fonction qui retourne comme X(n) faible nombre possible.

Je l'ai façon de comprendre la complexité du temps plus simple il mesure la plus courante pour le calcul de la complexité temporelle est la notation Big O. Cela supprime tous les facteurs constants de sorte que le temps d'exécution peut être estimée par rapport à N comme N tend vers l'infini. En général, vous pouvez penser comme ceci:

statement;

est constant. La durée de l'instruction ne changera pas par rapport à N

for ( i = 0; i < N; i++ )
  statement;

est linéaire. Le temps de fonctionnement de la boucle est directement proportionnelle à N. Lorsque N double, plus le temps de fonctionnement.

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

est quadratique. La durée des deux boucles est proportionnelle au carré de l'exécution N. Lorsque N double, le temps augmente en cours d'exécution par N * N.

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

est logarithmique. Le temps d'exécution de l'algorithme est proportionnel au nombre de fois N peut être divisé par 2. En effet, l'algorithme divise la zone de travail en deux à chaque itération.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

est N * log (N). Le temps d'exécution est constitué de boucles de N (itératif ou récursif) qui sont logarithmique, donc l'algorithme est une combinaison de linéaires et logarithmiques.

En général, faire quelque chose avec chaque élément dans une dimension linéaire, faire quelque chose avec tous les éléments en deux dimensions est quadratique, et en divisant la zone de travail dans la moitié est logarithmique. Il existe d'autres mesures Big O telles que la racine cubique, exponentielle et carré, mais ils sont loin d'être aussi commun. notation Big O est décrit comme O () où est la mesure. L'algorithme de tri rapide serait décrit comme (log N * (N)) O.

Note: Rien de tout cela a pris en compte le mieux, en moyenne, et les pires mesures de cas. Chacun aurait sa propre notation Big O. A noter également que c'est une explication très simpliste. Big O est le plus courant, mais il est aussi plus complexe que je l'ai montré. Il y a aussi d'autres notations telles que Omega grand, petit a, et grand thêta. Vous ne serez probablement pas les rencontrer en dehors d'un cours d'analyse de l'algorithme.

Voir plus:

Dites que vous commandez Harry Potter: Complete Collection 8-Film [Blu-ray] d'Amazon et de télécharger la même collection de films en ligne en même temps. Vous voulez tester la méthode est plus rapide. La livraison prend presque un jour pour arriver et le téléchargement terminé environ 30 minutes plus tôt. Génial! Il est donc une course serrée.

Et si je commande plusieurs films Blu-ray comme Le Seigneur des Anneaux, Crépuscule, The Dark Knight Trilogy, etc. et télécharger tous les films en ligne en même temps? Cette fois-ci, la livraison prend encore un jour pour terminer, mais le téléchargement en ligne dure 3 jours pour terminer. Pour les achats en ligne, le nombre d'article acheté (entrée) ne modifie pas le délai de livraison. La sortie est constante. Nous appelons O (1) .

Pour le téléchargement en ligne, le temps de téléchargement est directement proportionnelle à la taille des fichiers vidéo (entrée). Nous appelons O (n) .

D'après les expériences, nous savons que les achats en ligne échelles mieux que le téléchargement en ligne. Il est très important de comprendre la notation grand O, car il vous aide à analyser évolutivité et Efficacité d'algorithmes.

Remarque: notation Big O représente le pire scénario d'un algorithme. Supposons que O (1) et O (n) sont les pires scénarios de l'exemple ci-dessus.

Référence : http://carlcheo.com/compsci

Si vous avez une idée appropriée de l'infini dans votre tête, puis il y a une très brève description:

notation Big O vous indique le coût de la résolution d'un problème infiniment grand.

Par ailleurs

facteurs constants sont négligeables

Si vous mettez à niveau à un ordinateur qui peut exécuter votre algorithme deux fois plus rapide notation, grand O ne sera pas remarqué. l'amélioration des facteurs constants sont trop petites pour être même remarqué dans l'échelle que la notation grand O fonctionne avec. Notez que ceci est une partie intentionnelle de la conception de la notation grand O.

Bien que quoi que ce soit « plus » qu'un facteur constant peut être détectée, cependant.

Si vous êtes intéressés à faire des calculs dont la taille est « grande » assez pour être considéré comme environ l'infini, alors grande notation O est à peu près le coût de la résolution de votre problème.

Si ce qui précède n'a pas de sens, alors vous n'avez pas une notion intuitive compatible de l'infini dans votre tête, et vous ne devriez probablement pas tenir compte de ce qui précède; la seule façon que je connaisse pour rendre ces idées rigoureuses, ou de les expliquer si elles ne sont pas déjà intuitivement utile, est d'abord vous enseigner la notation grand O ou quelque chose de similaire. (Bien que, une fois que vous comprenez bien la notation grand O à l'avenir, il peut être utile de revoir ces idées)

Qu'est-ce qu'une explication de la notation anglais simple « Big O »?

Note très rapide:

L'O dans « Big O » désigne comme « ordre » (ou précisément « ordre de »)
de sorte que vous pourriez obtenir son idée littéralement qu'il est utilisé pour commander quelque chose pour les comparer.

"Big O" fait deux choses:
1. estimation approximative du nombre étapes de la méthode de votre ordinateur applique pour accomplir une tâche.
2. Faciliter le processus de comparer avec les autres afin de déterminer si elle est bonne ou non?
3. "Big O » atteint ce qui précède deux avec standard Notations.
Il y a sept notations les plus utilisées
1. O (1), signifie que votre ordinateur est une tâche fait avec pas 1, il est excellent, n ° 1 Ordonné
2. O (logN), signifie que votre ordinateur accomplir une tâche avec étapes, son logN bien, Ordonné n ° 2
3. O (N), terminer une tâche avec étapes, son N juste, ordre n ° 3
4. O (NlogN), met fin à une tâche pas O(NlogN), il est pas bon, ordre No.4
5. O (N ^ 2), une tâche se fait avec pas N^2, il est mauvais, ordre No.5
6. O (2 ^ N), obtenir une tâche fait avec pas 2^N, il est horrible, ordre No.6
7. O (N!), Obtenir une tâche fait avec pas N!, il est terrible, ordre No.7

Supposons que vous obtenez la notation O(N^2), non seulement vous êtes clair que la méthode prend des mesures N * N pour accomplir une tâche, vous voyez que ce n'est pas bon que de son classement <=>.

S'il vous plaît noter l'ordre à la fin de la ligne, juste pour vos meilleurs plus de 7 notations de understanding.There si toutes les possibilités envisagées.

Dans CS, l'ensemble des étapes pour accomplir une tâche est appelée algorithmes.
Dans la terminologie, la notation Big O est utilisé pour décrire la performance ou la complexité d'un algorithme.

En outre, Big O établit le pire des cas ou mesurer les étapes supérieures:.
Vous pouvez consulter Big-Ω (Big-Omega) pour le meilleur des cas.

Big-Ω ( notation Big-Omega) (article) | Khan Academy

Résumé « Big O » décrit les performances de l'algorithme et l'évalue.

ou répondre formellement, « Big O » classe les algorithmes et de normaliser le processus de comparaison.

manière la plus simple regarder (en anglais simple)

Nous essayons de voir comment le nombre de paramètres d'entrée, affecte la durée de fonctionnement d'un algorithme. Si le temps d'exécution de votre application est proportionnelle au nombre de paramètres d'entrée, il est dit à Big O n.

La déclaration ci-dessus est un bon début, mais pas tout à fait vrai.

Une explication plus précise (mathématique)

Supposons

n = nombre de paramètres d'entrée

T (n) = la fonction réelle qui exprime le temps d'exécution de l'algorithme en fonction de n

c = une constante

f (n) = une fonction approximative qui exprime le temps d'exécution de l'algorithme en fonction de n

Alors que jusqu'à Big O est concerné, l'approximation f (n) est considéré comme assez bon aussi longtemps que la condition ci-dessous est vrai.

lim     T(n) ≤ c×f(n)
n→∞

L'équation est lue comme Lorsque n tend vers l'infini, T n, est inférieur ou égal à c fois f de n.

En grande notation O, on écrira

T(n)∈O(n)

est lu comme T n est en grande O n.

Retour à l'anglais

D'après la définition mathématique ci-dessus, si vous dites que votre algorithme est un Big O n, cela signifie qu'il est fonction de n (nombre de paramètres d'entrée) ou plus rapide . Si votre algorithme est de Big O n, il est alors automatiquement le Big O de la place n.

Big O n veut dire que mon algorithme fonctionne au moins aussi vite que cela. Vous ne pouvez pas regarder la notation Big O de votre algorithme et dire son lent. Vous ne pouvez dire que son rapide.

Vérifier cette pour un tutoriel vidéo sur Big O de l'UC Berkley. Il est est en fait un concept simple. Si vous entendez le professeur Shewchuck (alias Dieu professeur de niveau) expliquant, vous direz « Oh, c'est tout ce qu'il est! ».

J'ai trouvé une explication vraiment super sur la notation grand O surtout pour une personne qui n'a pas beaucoup en mathématiques.

https: // rob- bell.net/2009/06/a-beginners-guide-to-big-o-notation/

notation Big O est utilisé en informatique pour décrire la performance   ou la complexité d'un algorithme. Big O décrit spécifiquement la   pire scénario, et peut être utilisé pour décrire le temps d'exécution   requise ou l'espace utilisé (par exemple, en mémoire ou sur disque) par un   algorithme.

Tous ceux qui ont lu Les perles de programmation ou toute autre science informatique   livres et ne possède pas de terre en mathématiques auront frappé un mur   quand ils ont atteint les chapitres qui mentionnent O (log N N) ou toute autre apparence   syntaxe fou. Espérons que cet article vous aidera à obtenir un   compréhension des bases de Big O et logarithmes.

En tant que programmeur premier et un second (ou peut-être troisième mathématique ou   quatrième) J'ai trouvé la meilleure façon de comprendre Big O était bien à   produire quelques exemples dans le code. Alors, voici quelques commandes communes de   la croissance ainsi que des descriptions et des exemples, si possible.

O (1)

O (1) décrit un algorithme qui exécute toujours dans le même temps   (Ou espace) quelle que soit la taille de l'ensemble de données d'entrée.
bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null; } O(N)
O (N)

O (N) décrit un algorithme dont le rendement va croître linéairement et   en proportion directe avec la taille de l'ensemble de données d'entrée. L'exemple   ci-dessous montre également comment Big O favorise la performance du pire   scénario; une chaîne de correspondance n'a pu être trouvée au cours d'une itération de la   pour la boucle et la fonction serait revenir au début, mais la notation Big O sera   toujours supposer la limite supérieure où l'algorithme effectue la   nombre maximum d'itérations.
bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 
O (N ²)

O (N ²) représente un algorithme dont le rendement est directement   proportionnelle au carré de la taille de l'ensemble de données d'entrée. C'est   commun avec des algorithmes qui impliquent des itérations imbriquées sur les données   ensemble. itérations imbriquées plus profond se traduira par O (N ³), O (N ⁴) etc.
bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}
O (2 ^N)

O (2 ^N) désigne un algorithme dont la croissance double à chaque additon à   les données d'entrée définies. La courbe de croissance d'une fonction O (2 ^N) est   exponentielle - à partir de très peu profonde, puis la hausse météoriques. Un   exemple d'une fonction O (2 ^N) est le calcul récursif de Fibonacci   numéros:
int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}
logarithmes

logarithmes sont un peu plus délicat à expliquer, donc je vais utiliser un commun   exemple:

recherche binaire est une technique utilisée pour rechercher des ensembles de données triées. Ça marche   en sélectionnant l'élément central de l'ensemble de données, essentiellement la   médiane et il se compare à une valeur cible. Si les valeurs correspondent il   retournera le succès. Si la valeur cible est supérieure à la valeur de   l'élément palpeur, il faudra la moitié supérieure de l'ensemble de données et   effectuer la même opération contre elle. De même, si la valeur cible   est inférieure à la valeur de l'élément de sonde, il se produira le   opération contre la moitié inférieure. Elle continuera de réduire de moitié les données   mettre à chaque itération jusqu'à ce que la valeur a été trouvée ou jusqu'à ce qu'il puisse   pas plus divisé l'ensemble de données.

Ce type d'algorithme est décrit comme O (log N). La réduction de moitié itérative   des ensembles de données décrits dans l'exemple de recherche binaire produit une croissance   courbe qui culmine au début et aplatit lentement que la taille   des ensembles de données augmentent par exemple un ensemble de données d'entrée contenant des 10 articles   prend une seconde pour compléter un ensemble de données contenant des éléments 100 prend   deux secondes, et un ensemble de données contenant 1000 articles aura trois   secondes. Doubler la taille de l'ensemble de données d'entrée a peu d'effet sursa croissance après une seule itération de l'algorithme de l'ensemble de données   sera réduit de moitié et donc sur un pied d'égalité avec une donnée d'entrée mis la moitié de la   Taille. Cela fait des algorithmes comme la recherche binaire extrêmement efficace   lorsqu'ils traitent avec de grands ensembles de données.

Ceci est une explication très simplifiée, mais j'espère qu'il couvre les détails les plus importants.

Disons que votre algorithme traitant du problème dépend de certains « facteurs », par exemple, nous allons le rendre N et X.

En fonction de N et X, votre algorithme nécessite certaines opérations, par exemple, dans le pire des cas, il est des opérations 3(N^2) + log(X).

Depuis Big-O ne se soucie pas trop de facteur constant (aka 3), le Big-O de votre algorithme est O(N^2 + log(X)). Il se traduit essentiellement la quantité d'opérations votre algorithme a besoin pour le pire des cas échelles avec ce '.

Préface

algorithme:procédure/formule pour résoudre un problème

Comment analyser les algorithmes et comment comparer les algorithmes les uns aux autres ?

exemple: vous et un ami êtes invités à créer une fonction pour additionner les nombres de 0 à N.Vous proposez f(x) et votre ami propose g(x).Les deux fonctions ont le même résultat, mais un algorithme différent.Afin de comparer objectivement l’efficacité des algorithmes que nous utilisons Notation Big-O.

Notation Big-O : décrit à quelle vitesse le temps d'exécution augmentera par rapport à l'entrée à mesure que l'entrée devient arbitrairement grande.

3 points clés à retenir :

Comparer à quelle vitesse le temps d'exécution augmente PAS comparer les durées d'exécution exactes (dépend du matériel)
Concerné uniquement par la croissance du temps d'exécution par rapport à l'entrée (n)
Comme n devient arbitrairement grand, concentrez-vous sur les termes qui croîtront le plus rapidement à mesure que n grandit (pensez à l'infini) AKA analyse asymptotique

Complexité spatiale : Outre la complexité temporelle, nous nous soucions également de la complexité spatiale (la quantité de mémoire/d'espace utilisée par un algorithme).Au lieu de vérifier le temps des opérations, nous vérifions la taille de l'allocation de mémoire.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow

Qu'est-ce qu'une explication en anglais simple de la notation « Big O » ?

Le Livre Téléphone

Le Travelling Salesman

polynomiale

O (1)

O (N)

O (N 2 )

O (2 N )

logarithmes

Préface

O (N ²)

O (2 ^N)