Je préférerais aussi peu de définition formelle que possible et des mathématiques simples.

Remarque rapide, cela confond presque certainement la notation Big O (qui est une borne supérieure) avec la notation Thêta "Θ" (qui est une borne bilatérale). D'après mon expérience, cela est en fait typique des discussions dans des contextes non universitaires. Toutes mes excuses pour toute confusion causée.

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

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

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

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

• relatif: vous ne pouvez comparer les pommes qu'aux pommes. Vous ne pouvez pas comparer un algorithme pour effectuer une 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 d'observations ou d'hypothèses. Par exemple, les algorithmes de tri sont généralement comparés sur la base d'opérations de comparaison (comparer deux nœuds pour déterminer leur ordre relatif). Cela suppose que la comparaison coûte cher. Mais que faire si la comparaison est bon marché mais que l'échange est cher? Cela change la comparaison; et
• complexité: s'il me faut une seconde pour trier 10 000 éléments, combien de temps me faudra-t-il pour trier un million? La complexité dans ce cas est une mesure relative à autre chose.

Revenez et relisez ce qui précède après avoir lu le reste.

Le meilleur exemple de Big-O auquel je puisse penser est l'arithmétique. Prenez deux nombres (123456 et 789012). Les opérations arithmétiques de base que nous avons apprises à l'école étaient les suivantes:

• une addition;
• soustraction;
• multiplication; et
• division.

Chacun d'eux est une opération ou un problème. Une méthode pour les résoudre s'appelle un algorithme .

L'addition est la plus simple. Vous alignez les chiffres (à droite) et ajoutez les chiffres dans une colonne en écrivant le dernier numéro de cet ajout dans le résultat. La partie «dizaines» de ce nombre est reportée à la colonne suivante.

Supposons que l'ajout de ces nombres soit l'opération la plus coûteuse de cet algorithme. Il va de soi que pour additionner ces deux nombres, nous devons additionner ensemble 6 chiffres (et éventuellement porter un 7e). Si nous additionnons deux nombres à 100 chiffres, nous devons faire 100 ajouts. Si nous ajoutons deux numéros à 10 000 chiffres, nous devons faire 10 000 ajouts.

Voir le motif? La complexité (étant le nombre d'opérations) est directement proportionnelle au nombre de chiffres n dans le plus grand nombre. Nous appelons cela O (n) ou complexité linéaire .

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

La multiplication est différente. Vous alignez les nombres, prenez le premier chiffre du nombre inférieur et multipliez-le tour à tour contre chaque chiffre du nombre supérieur et ainsi de suite à travers chaque chiffre. Donc, pour multiplier nos deux nombres à 6 chiffres, nous devons faire 36 multiplications. Nous devrons peut-être faire jusqu'à 10 ou 11 ajouts de colonnes pour obtenir le résultat final aussi.

Si nous avons deux nombres à 100 chiffres, nous devons faire 10 000 multiplications et 200 additions. Pour deux nombres à un million de chiffres, nous devons faire un billion (10 ¹² ) multiplications et deux millions d'ajouts.

Comme l'algorithme évolue avec n au carré , il s'agit de la complexité O (n ² ) ou quadratique . C'est le bon moment pour présenter un autre concept important:

Nous ne nous soucions que de la partie la plus importante de la complexité.

Les astucieux ont peut-être réalisé que nous pouvions exprimer le nombre d'opérations comme: n ² + 2n. Mais comme vous l'avez vu dans notre exemple avec deux nombres d'un million de chiffres chacun, le deuxième terme (2n) devient insignifiant (représentant 0,0002% du total des opérations à ce stade).

On peut remarquer que nous avons supposé le pire des cas ici. En multipliant les nombres à 6 chiffres, si l'un d'eux a 4 chiffres et l'autre a 6 chiffres, alors nous n'avons que 24 multiplications. Néanmoins, nous calculons le pire des scénarios pour ce «n», c'est-à-dire lorsque les deux sont des nombres à 6 chiffres. La notation Big-O concerne donc le pire scénario d'un algorithme.

L'annuaire téléphonique

Le deuxième meilleur exemple auquel je peux penser est l'annuaire téléphonique, normalement appelé les pages blanches ou similaire, mais il varie d'un pays à l'autre. Mais je parle de celui qui répertorie les gens par nom, puis par initiales ou prénom, éventuellement par adresse et ensuite par numéro de téléphone.

Maintenant, si vous demandiez à un ordinateur de rechercher le numéro de téléphone de "John Smith" dans un annuaire téléphonique contenant 1 000 000 de noms, que feriez-vous? Ignorant le fait que vous pouviez deviner jusqu'où les S ont commencé (supposons que vous ne pouvez pas), que feriez-vous?

Une implémentation typique pourrait être d'ouvrir au milieu, de prendre le 500 000 ^e et de le comparer à "Smith". S'il se trouve que c'est "Smith, John", nous avons vraiment eu de la chance. Il est beaucoup plus probable que "John Smith" soit avant ou après ce nom. Si c'est après, nous divisons la dernière moitié du répertoire en deux et répétons. Si c'est avant, nous divisons la première moitié de l'annuaire en deux et répétons. Etc.

Cela s'appelle une 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, vous pouvez réellement trouver n'importe quel nom en le faisant au maximum 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 en faut 4.
• …
• Pour 1000000, il en faut 20.

C'est incroyablement bon, n'est-ce pas?

En termes Big-O, il s'agit de la complexité O (log n) ou logarithmique . Maintenant, le logarithme en question pourrait être ln (base e), log ₁₀ , log ₂ ou une autre base. Peu importe que ce soit toujours O (log n) tout comme O (2n ² ) et O (100n ² ) sont toujours tous les deux O (n ² ).

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

• Meilleur cas: Dans la recherche dans l'annuaire téléphonique, le meilleur cas est que nous trouvions le nom dans une seule comparaison. C'est O (1) ou complexité constante ;
• Cas attendu: Comme indiqué ci-dessus, il s'agit de O (log n); et
• Pire cas: il s'agit également de O (log n).

Normalement, nous ne nous soucions pas du meilleur cas. Nous sommes intéressés par le pire et le plus attendu. Parfois, l'un ou l'autre de ces éléments sera plus important.

Retour à l'annuaire téléphonique.

Et si vous avez un numéro de téléphone et que vous souhaitez trouver un nom? La police a un annuaire téléphonique inversé, mais ces recherches sont refusées au grand public. Ou sont-ils? Techniquement, vous pouvez inverser la recherche d'un numéro dans un annuaire téléphonique ordinaire. Comment?

Vous commencez par le prénom et comparez le nombre. Si c'est un match, tant mieux, sinon, vous passez au suivant. Vous devez le faire de cette façon car l'annuaire téléphonique n'est pas ordonné (par numéro de téléphone de toute façon).

Donc, pour trouver un nom en fonction du numéro de téléphone (recherche inversée):

• Meilleur cas: O (1);
• Cas prévu: O (n) (pour 500 000); et
• Pire cas: O (n) (pour 1000000).

Le voyageur de commerce

C'est un problème assez connu en informatique et mérite une mention. Dans ce problème, vous avez N villes. Chacune de ces villes est reliée à une ou plusieurs autres villes par une route d'une certaine distance. Le problème du voyageur de commerce est de trouver le circuit le plus court qui visite chaque ville.

Cela semble 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

Eh 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.

• Emmenez-le dans 4 villes et vous avez (iirc) 12 possibilités.
• Avec 5, c'est 60.
• 6 devient 360.

C'est une fonction d'une opération mathématique appelée factorielle . Fondamentalement:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
• 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
• …
• 25! = 25 × 24 ×… × 2 × 1 = 15.511.210.043.330.985.984.000.000
• …
• 50! = 50 × 49 ×… × 2 × 1 = 3,04140932 × 10 ⁶⁴

Le problème du Big-O du voyageur de commerce est donc la complexité O (n!) Ou factorielle ou combinatoire .

Au moment où vous arrivez dans 200 villes, il ne reste plus assez de temps dans l'univers pour résoudre le problème avec les ordinateurs traditionnels.

Quelque chose à quoi penser.

Temps polynomial

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

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

Quoi qu'il en soit, c'est tout pour mon explication (espérons-le en anglais ordinaire) de Big O (révisée).

Il montre comment un algorithme évolue en fonction de la taille d'entrée.

O (n ² ) : connu sous le nom de complexité quadratique

• 1 élément: 1 seconde
• 10 éléments: 100 secondes
• 100 éléments: 10000 secondes

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

O (n) : connu sous le nom de complexité linéaire

• 1 élément: 1 seconde
• 10 éléments: 10 secondes
• 100 éléments: 100 secondes

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

O (1) : connu sous le nom de complexité constante

• 1 élément: 1 seconde
• 10 éléments: 1 seconde
• 100 éléments: 1 seconde

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

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

• 1 élément: 1 seconde
• 10 éléments: 2 secondes
• 100 éléments: 3 secondes
• 1000 éléments: 4 secondes
• 10000 éléments: 5 secondes

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

Voilà l'essentiel. Ils réduisent les calculs afin que ce ne soit pas exactement n ² ou ce qu'ils disent, mais ce sera le facteur dominant dans la mise à l'échelle.

La notation Big-O (également appelée notation «croissance asymptotique») est ce à quoi les fonctions «ressemblent» lorsque vous ignorez les facteurs constants et les éléments proches de l'origine . Nous l'utilisons pour parler de la façon dont les choses évoluent .

Les bases

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

• f(x) ∈ O(upperbound)signifie f"ne pousse pas plus vite que"upperbound
• f(x) ∈ Ɵ(justlikethis)signifie f"pousse exactement comme"justlikethis
• f(x) ∈ Ω(lowerbound)signifie f"ne pousse pas plus lentement que"lowerbound

La notation big-O ne se soucie pas des facteurs constants: 9x²on dit que la fonction "croît exactement comme" 10x². La notation asymptotique big-O ne se soucie pas non plus des éléments non asymptotiques ("éléments proches de l'origine" ou "ce qui se passe lorsque la taille du problème est petite"): la fonction 10x²est censée "croître exactement comme" 10x² - x + 2.

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

Autrement dit, tout tourne autour du rapport à l'infini. Si vous divisez le temps réel que cela prend par le O(...), vous obtiendrez un facteur constant dans la limite des grandes entrées. Intuitivement, cela a du sens: les fonctions «évoluent comme» si vous pouvez multiplier l'une pour obtenir l'autre. C'est à ce moment que nous disons ...

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

... cela signifie que pour les tailles de problème N "assez grandes" (si nous ignorons les choses près de l'origine), il existe une constante (par exemple 2,5, complètement composée) telle que:

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

Il existe de nombreux choix de constante; souvent le "meilleur" choix est connu comme le "facteur constant" de l'algorithme ... mais nous l'ignorons souvent comme nous ignorons les termes non plus grands (voir la section Facteurs constants pour savoir pourquoi ils n'ont généralement pas d'importance). Vous pouvez également considérer l'équation ci-dessus comme une limite, en disant: « Dans le pire des cas, le temps qu'il faudra ne sera jamais pire qu'en gros N*log(N), dans un facteur de 2,5 (un facteur constant dont nous ne nous soucions pas beaucoup) » .

En général, O(...)c'est le plus utile car nous nous soucions souvent du pire des cas. Si f(x)représente quelque chose de "mauvais" comme l'utilisation du processeur ou de la mémoire, alors " f(x) ∈ O(upperbound)" signifie " upperboundest le pire des cas d'utilisation du processeur / de la mémoire".

Applications

En tant que construction purement mathématique, la notation big-O ne se limite pas à parler de temps de traitement et de mémoire. Vous pouvez l'utiliser pour discuter des asymptotiques de tout élément où la mise à l'échelle est significative, comme:

• le nombre de poignées de main possibles entre les Npersonnes lors d'une fête ( Ɵ(N²), en particulier N(N-1)/2, mais ce qui importe, c'est que cela "évolue comme" N²)
• nombre probabiliste attendu de personnes ayant vu un marketing viral en fonction du temps
• comment la latence du site Web évolue avec le nombre d'unités de traitement dans un processeur, un processeur graphique ou un cluster d'ordinateurs
• comment la production de chaleur évolue sur le processeur meurt en fonction du nombre de transistors, de la tension, etc.
• le temps nécessaire à un algorithme pour fonctionner, en fonction de la taille d'entrée
• l'espace requis par un algorithme pour fonctionner, en fonction de la taille d'entrée

Exemple

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

Sauvegardez un peu: le nombre de poignées de main est exactement n-choisissez-2 ou N*(N-1)/2(chacune des N personnes serre la main de N-1 autres personnes, mais cette poignée de main double compte donc divisez par 2):

Cependant, pour un très grand nombre de personnes, le terme linéaire Nest éclipsé et contribue efficacement à 0 au rapport (dans le graphique: la fraction des cases vides sur la diagonale par rapport au total des cases diminue à mesure que le nombre de participants augmente). Par conséquent, le comportement de mise à l'échelle est order N², ou le nombre de poignées de main "croît comme N²".

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

C'est comme si les cases vides sur la diagonale du graphique (N * (N-1) / 2 coches) n'étaient même pas là (N ² coches asymptotiquement).

(digression temporaire de "anglais ordinaire" :) Si vous vouliez le prouver par vous-même, vous pourriez effectuer une algèbre simple sur le rapport pour le diviser en plusieurs termes ( limsignifie "considéré dans la limite de", ignorez-le si vous je ne l'ai pas vu, c'est juste une notation pour "et N est vraiment très gros"):

    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 poignées de main 'ressemble tellement à' x² pour les grandes valeurs, que si nous devions écrire le ratio # poignées de main / x², le fait que nous n'ayons pas besoin exactement de x² poignées de main n'apparaîtrait même pas dans la décimale pour un tout arbitrairement grand.

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

Construire l'intuition

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

"Pour une taille d'entrée suffisamment grande = N, quel que soit le facteur constant, si je double la taille d'entrée ...

• ... Je double le temps qu'un algorithme O (N) ("temps linéaire") prend. "

  N → (2N) = 2 ( N )

• ... Je double au carré (quadruple) le temps d' un O (N²) ( "time quadratique") algorithme prend. » (Par exemple , un problème aussi grand 100x prend 100² = 10000x aussi longtemps ... peut - être non viable)

  N² → (2N) ² = 4 ( N² )

• ... J'ai doublé (octuple) le temps nécessaire à un algorithme O (N³) ("temps cubique"). " (Par exemple, un problème 100x aussi gros prend 100³ = 1000000x aussi longtemps ... très insoutenable)

  cN³ → c (2N) ³ = 8 ( cN³ )

• ... J'ajoute un montant fixe au temps qu'un algorithme O (log (N)) ("temps logarithmique") prend. " (Pas cher!)

  c log (N) → c log (2N) = (c log (2)) + ( c log (N) ) = (montant fixe) + ( c log (N) )

• ... Je ne change pas le temps que prend un algorithme O (1) ("temps constant"). " (Le moins cher!)

  c * 1 → c * 1

• ... "je" double (fondamentalement) "le temps nécessaire à un algorithme O (N log (N))." (Assez courant)

  il est inférieur à O (N ^1.000001 ), que vous pourriez appeler fondamentalement linéaire

• ... J'augmente ridiculement le temps qu'un algorithme O (2 ^N ) ("temps exponentiel") prend. " (Vous doubleriez (ou tripler, etc.) le temps juste en augmentant le problème d'une seule unité)

  2 ^N → 2 ^2N = (4 ^N ) ............ autrement dit ...... 2 ^N → 2 ^{N + 1} = 2 ^N 2 ¹ = 2 2 ^N

[pour les inclinés mathématiquement, vous pouvez passer la souris sur les spoilers pour les sidenotes mineures]

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

(techniquement, le facteur constant pourrait peut-être avoir de l'importance dans certains exemples plus ésotériques, mais j'ai formulé les choses ci-dessus (par exemple, dans log (N)) de telle sorte que ce ne soit pas le cas)

Ce sont les ordres de croissance du pain et du beurre que les programmeurs et les informaticiens appliqués utilisent comme points de référence. Ils les voient tout le temps. (Donc, alors que vous pourriez penser techniquement "Doubler l'entrée rend un algorithme O (√N) 1,414 fois plus lent", il vaut mieux le considérer comme "c'est pire que logarithmique mais meilleur que linéaire".)

Facteurs constants

Habituellement, nous ne nous soucions pas des facteurs constants spécifiques, car ils n'affectent pas la façon dont la fonction se développe. Par exemple, deux algorithmes peuvent tous deux prendre du O(N)temps, mais l'un peut être deux fois plus lent que l'autre. Nous ne nous soucions généralement pas trop, sauf si le facteur est très important, car l'optimisation est une affaire délicate ( quand l'optimisation est-elle prématurée? ); aussi le simple fait de choisir un algorithme avec un meilleur big-O améliorera souvent les performances par ordre de grandeur.

Certains algorithmes asymptotiquement supérieurs (par exemple, un O(N log(log(N)))tri sans comparaison ) peuvent avoir un facteur constant (par exemple 100000*N log(log(N))) ou un surcoût relativement important comme O(N log(log(N)))avec un caché + 100*N, qui valent rarement la peine d'être utilisés, même sur des données volumineuses.

Pourquoi O (N) est parfois le meilleur que vous puissiez faire, c'est-à-dire pourquoi nous avons besoin d'infrastructures de données

O(N)les algorithmes sont en quelque sorte les "meilleurs" algorithmes si vous avez besoin de lire toutes vos données. L' acte même de lire un tas de données est une O(N)opération. Le chargement en mémoire est généralement O(N)(ou plus rapide si vous avez un support matériel, ou pas de temps du tout si vous avez déjà lu les données). Cependant, si vous touchez ou même regardez chaque élément de données (ou même tous les autres éléments de données), votre algorithme prendra du O(N)temps pour effectuer cette recherche. Peu importe le temps que prend votre algorithme, ce sera au moins O(N)parce qu'il a passé ce temps à regarder toutes les données.

Il en va de même pour l' acte même d'écrire . Tous les algorithmes qui impriment N choses prendront N temps car la sortie est au moins aussi longue (par exemple, imprimer toutes les permutations (façons de réorganiser) un ensemble de N cartes à jouer est factoriel:) O(N!).

Cela motive l'utilisation de structures de données : une structure de données nécessite la lecture des données une seule fois (généralement du O(N)temps), plus une quantité arbitraire de prétraitement (par exemple O(N)ou O(N log(N))ou O(N²)) que nous essayons de garder petite. Par la suite, la modification de la structure des données (insertions / suppressions / etc.) et les requêtes sur les données prennent très peu de temps, comme O(1)ou O(log(N)). Vous procédez ensuite à un grand nombre de requêtes! En général, plus vous êtes prêt à travailler à l'avance, moins vous aurez à faire plus tard.

Par exemple, supposons que vous disposiez des coordonnées de latitude et de longitude de millions de segments de route et que vous vouliez trouver toutes les intersections de rues.

• Méthode naïve: si vous aviez les coordonnées d'une intersection de rues et que vous vouliez examiner les rues voisines, vous devriez parcourir les millions de segments à chaque fois et vérifier chacun pour la contiguïté.
• Si vous ne deviez faire cela qu'une seule fois, ce ne serait pas un problème de devoir faire la méthode de O(N)travail naïve une seule fois, mais si vous voulez le faire plusieurs fois (dans ce cas, Nfois, une fois pour chaque segment), nous 'aurais à faire du O(N²)travail, soit 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 table de hachage (une table de recherche à vitesse instantanée, également connue sous le nom de table de hachage ou dictionnaire), nous payons un petit coût en prétraitant tout à O(N)temps. Par la suite, il ne faut en moyenne qu'un temps constant pour rechercher quelque chose par sa clé (dans ce cas, notre clé est les coordonnées de latitude et de longitude, arrondies dans une grille; nous recherchons les espaces de grille adjacents dont il n'y a que 9, ce qui est un constant).
• Notre tâche est passée de l'impossible O(N²)à la gérable O(N), et tout ce que nous avions à faire était de payer un coût mineur pour fabriquer une table de hachage.
• analogie : L'analogie dans ce cas particulier est un casse-tête: nous avons créé une structure de données qui exploite certaines propriétés des données. Si nos segments de route sont comme des pièces de puzzle, nous les groupons en faisant correspondre la couleur et le motif. Nous exploitons ensuite cela pour éviter de faire un travail supplémentaire plus tard (en comparant des pièces de puzzle de même couleur les unes aux autres, pas à toutes les autres pièces de puzzle).

Morale de l'histoire: une structure de données permet d'accélérer les opérations. De plus, les structures de données avancées peuvent vous permettre de combiner, retarder ou même ignorer des opérations de manière incroyablement intelligente. Différents problèmes auraient des analogies différentes, mais ils impliqueraient tous d'organiser les données d'une manière qui exploite une structure qui nous tient à cœur ou que nous lui avons artificiellement imposée pour la comptabilité. Nous travaillons à l'avance (essentiellement la planification et l'organisation), et maintenant les tâches répétées sont beaucoup plus faciles!

Exemple pratique: visualisation des ordres de croissance lors du codage

La notation asymptotique est, à la base, bien distincte de la programmation. La notation asymptotique est un cadre mathématique pour réfléchir à la façon dont les choses évoluent et peut être utilisée dans de nombreux domaines différents. Cela dit ... c'est ainsi que vous appliquez la notation asymptotique au codage.

Les bases: chaque fois que nous interagissons avec chaque élément d'une collection de taille A (comme un tableau, un ensemble, toutes les clés d'une carte, etc.), ou effectuons des itérations A d'une boucle, c'est un facteur multiplicatif de taille A Pourquoi est-ce que je dis "un facteur multiplicatif"? - parce que les boucles et les fonctions (presque par définition) ont un temps d'exécution multiplicatif: le nombre d'itérations, le temps de travail effectué dans la boucle (ou pour les fonctions: le nombre de fois que vous appelez le fonction, temps de travail effectué dans la fonction). (Cela vaut si nous ne faisons rien de fantaisiste, comme sauter des boucles ou quitter la boucle tôt, ou changer le flux de contrôle dans la fonction en fonction d'arguments, ce qui est très courant.) Voici quelques exemples de techniques de visualisation, avec un pseudocode d'accompagnement.

(ici, les xs représentent des unités de travail à temps constant, des instructions de processeur, des opcodes d'interprète, peu importe)

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 de légèrement compliqué, vous pourrez peut-être encore 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 plus petit contour reconnaissable que vous puissiez dessiner est ce qui compte; un triangle est une forme bidimensionnelle (0,5 A ^ 2), tout comme un carré est une forme bidimensionnelle (A ^ 2); le facteur constant de deux ici reste dans le rapport asymptotique entre les deux, cependant, nous l'ignorons comme tous les facteurs ... (Il y a quelques nuances malheureuses à cette technique que je n'entre pas ici; elle peut vous induire en erreur.)

Bien sûr, cela ne signifie pas que les boucles et les fonctions sont mauvaises; au contraire, ils sont les éléments constitutifs des langages de programmation modernes, et nous les aimons. Cependant, nous pouvons voir que la façon dont nous tissons les boucles et les fonctions et les conditions avec nos données (flux de contrôle, etc.) imite l'utilisation du temps et de l'espace de notre programme! Si l'utilisation du temps et de l'espace devient un problème, c'est lorsque nous recourons à l'intelligence et trouvons un algorithme facile ou une structure de données que nous n'avions pas envisagée, pour réduire l'ordre de croissance d'une manière ou d'une autre. Néanmoins, ces techniques de visualisation (bien qu'elles ne fonctionnent pas toujours) peuvent vous donner une supposition naïve au pire moment de l'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 que c'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 que vous enregistrez (N) passes des données, pour O (N * log (N)) temps total:

   <----------------------------- 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

Indépendamment mais mérite d'être mentionné à nouveau: si nous effectuons un hachage (par exemple une recherche de dictionnaire / de table de hachage), c'est un facteur de 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 avec une fonction récursive ou un algorithme de division et de conquête, vous pouvez utiliser le théorème maître (fonctionne généralement), ou dans des cas ridicules le théorème d'Akra-Bazzi (fonctionne presque toujours), vous recherchez le le temps d'exécution de votre algorithme sur Wikipedia.

Mais les programmeurs ne pensent pas comme ça car finalement, l'intuition de l'algorithme devient juste une seconde nature. Vous commencerez à coder quelque chose d'inefficace et penserez immédiatement "est-ce que je fais quelque chose de vraiment inefficace? ". Si la réponse est "oui" ET que vous prévoyez que cela compte réellement, vous pouvez prendre du recul et penser à diverses astuces pour accélérer les choses (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é).

Complexité amortie et moyenne

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

Cas moyen : ce n'est pas plus que d'utiliser la notation big-O pour la valeur attendue d'une fonction, plutôt que la fonction elle-même. Dans le cas habituel où vous considérez que toutes les entrées sont également probables, le cas moyen n'est que la moyenne du temps d'exécution. Par exemple avec quicksort, même si le pire des cas est O(N^2)pour certaines entrées vraiment mauvaises, le cas moyen est l'habituel O(N log(N))(les entrées vraiment mauvaises sont très peu nombreuses, si peu que nous ne les remarquons pas dans le cas moyen).

Pire cas amorti : certaines structures de données peuvent avoir une complexité du pire des cas qui est grande, mais garantissez que si vous effectuez un grand nombre de ces opérations, la quantité moyenne de travail que vous effectuez sera meilleure que dans le pire des cas. Par exemple, vous pouvez avoir une structure de données qui prend normalement un O(1)temps constant . Cependant, de temps en temps, il `` hoquetera '' et prendra du O(N)temps pour une opération aléatoire, car peut-être qu'il doit faire de la comptabilité ou de la collecte des ordures ou quelque chose ... mais il vous promet que s'il fait du hoquet, il ne recommencera pas pour N plus d'opérations. Le coût le plus défavorable est toujours O(N)par opération, mais le coût amorti sur de nombreuses séries est O(N)/N=O(1)par opération. Parce que les grandes opérations sont suffisamment rares, la quantité massive de travail occasionnel peut être considérée comme se mélangeant avec le reste du travail comme un facteur constant. On dit que le travail est "amorti" sur un nombre d'appels suffisamment important pour qu'il disparaisse asymptotiquement.

L'analogie avec l'analyse amortie:

Vous conduisez une voiture. Parfois, vous devez passer 10 minutes à aller à la station-service, puis passer 1 minute à remplir le réservoir de gaz. Si vous faisiez cela à chaque fois que vous alliez n'importe où avec votre voiture (passez 10 minutes en voiture jusqu'à la station-service, passez quelques secondes à remplir une fraction de gallon), ce serait très inefficace. Mais si vous remplissez le réservoir une fois tous les quelques jours, les 11 minutes passées en voiture jusqu'à la station-service sont "amorties" sur un nombre suffisamment important de trajets, que vous pouvez ignorer et prétendre que tous vos trajets étaient peut-être 5% plus longs.

Comparaison entre le cas moyen et le pire cas amorti:

• Cas moyen: nous faisons quelques hypothèses sur nos intrants; c'est-à-dire si nos entrées ont des probabilités différentes, alors nos sorties / temps d'exécution auront des probabilités différentes (dont nous prenons la moyenne). Habituellement, nous supposons que nos entrées sont toutes également probables (probabilité uniforme), mais si les entrées du monde réel ne correspondent pas à nos hypothèses d '«entrée moyenne», les calculs de sortie / d'exécution moyens peuvent être dénués de sens. Si vous prévoyez des entrées uniformément aléatoires, cela est utile de réfléchir!
• Le pire des cas amorti: Si vous utilisez une structure de données du pire cas amorti, les performances sont garanties d'être dans le pire des cas amortis ... éventuellement (même si les entrées sont choisies par un démon maléfique qui sait tout et essaie de vous défoncer). Habituellement, nous l'utilisons pour analyser des algorithmes qui peuvent être très «saccadés» en termes de performances avec de grands hoquets inattendus, mais avec le temps, ils fonctionnent aussi bien que d'autres algorithmes. (Cependant, à moins que votre structure de données n'ait des limites supérieures pour le travail exceptionnel qu'il est prêt à tergiverser, un attaquant maléfique pourrait peut-être vous forcer à rattraper le volume maximum de travail tergiversé à la fois.

Cependant, si vous êtes raisonnablement inquiet pour un attaquant, il y a de nombreux autres vecteurs d'attaque algorithmique dont vous devez vous soucier en plus de l'amortissement et du cas moyen.)

Le cas moyen et l'amortissement sont des outils incroyablement utiles pour penser et concevoir en tenant compte de la mise à l'échelle.

(Voir Différence entre le cas moyen et l'analyse amortie si vous êtes intéressé par ce sous-sujet.)

Big-O multidimensionnel

La plupart du temps, les gens ne réalisent pas qu'il y a plus d'une variable au travail. Par exemple, dans un algorithme de recherche de chaînes, votre algorithme peut prendre du temps O([length of text] + [length of query]), c'est-à-dire qu'il est linéaire en deux variables comme O(N+M). D'autres algorithmes plus naïfs peuvent être O([length of text]*[length of query])ou O(N*M). Ignorer plusieurs variables est l'une des omissions les plus courantes que je vois dans l'analyse d'algorithmes et peut vous handicaper lors de la conception d'un algorithme.

Toute l'histoire

Gardez à l'esprit que big-O n'est pas toute l'histoire. Vous pouvez accélérer considérablement certains algorithmes en utilisant la mise en cache, en les rendant sans mémoire cache, en évitant les goulots d'étranglement en travaillant avec la RAM au lieu du disque, en utilisant la parallélisation ou en travaillant à l'avance - ces techniques sont souvent indépendantes de l'ordre de croissance notation "big-O", bien que vous verrez souvent le nombre de cœurs dans la notation big-O des algorithmes parallèles.

Gardez également à l'esprit qu'en raison des contraintes cachées de votre programme, vous pourriez ne pas vraiment vous soucier du comportement asymptotique. Vous travaillez peut-être avec un nombre limité de valeurs, par exemple:

• Si vous triez quelque chose comme 5 éléments, vous ne voulez pas utiliser le O(N log(N))quicksort rapide ; vous souhaitez utiliser le tri par insertion, qui s'avère bien performant sur les petites entrées. Ces situations surviennent souvent dans des algorithmes de division et de conquête, où vous divisez le problème en sous-problèmes de plus en plus petits, tels que le tri récursif, les transformées de Fourier rapides ou la multiplication matricielle.
• Si certaines valeurs sont effectivement limitées en raison d'un fait caché (par exemple, le nom humain moyen est délicatement limité à peut-être 40 lettres, et l'âge humain est délicatement limité à environ 150). Vous pouvez également imposer des limites à votre saisie pour rendre les termes constants de manière efficace.

En pratique, même parmi les algorithmes qui ont des performances asymptotiques identiques ou similaires, leur mérite relatif peut en fait être dicté par d'autres choses, telles que: d'autres facteurs de performance (quicksort et mergesort sont les deux O(N log(N)), mais quicksort tire parti des caches CPU); considérations de non-performance, comme la facilité de mise en œuvre; si une bibliothèque est disponible et à quel point la bibliothèque est réputée et entretenue.

Les programmes s'exécuteront également plus lentement sur un ordinateur à 500 MHz par rapport à un ordinateur à 2 GHz. Nous ne considérons pas vraiment cela comme faisant partie des limites des ressources, car nous pensons à la mise à l'échelle en termes de ressources machine (par exemple par cycle d'horloge), pas par seconde réelle. Cependant, il y a des choses similaires qui peuvent affecter "secrètement" les performances, comme si vous exécutez sous émulation, ou si le code optimisé par le compilateur ou non. Cela peut rallonger certaines opérations de base (même les unes par rapport aux autres), voire accélérer ou ralentir certaines opérations de manière asymptotique (même les unes par rapport aux autres). L'effet peut être faible ou important entre différentes implémentations et / ou environnements. Changez-vous de langue ou de machine pour réaliser ce petit travail supplémentaire? Cela dépend d'une centaine d'autres raisons (nécessité, compétences, collègues, productivité du programmeur,

Les problèmes ci-dessus, comme l'effet du choix du langage de programmation utilisé, ne sont presque jamais considérés comme faisant partie du facteur constant (et ne devraient pas l'être); pourtant, il faut en être conscient car parfois (quoique rarement) elles peuvent affecter les choses. Par exemple, en cpython, l'implémentation native de la file d'attente prioritaire est asymptotiquement non optimale ( O(log(N))plutôt que O(1)pour votre choix d'insertion ou find-min); utilisez-vous une autre implémentation? Probablement pas, car l'implémentation C est probablement plus rapide, et il y a probablement d'autres problèmes similaires ailleurs. Il y a des compromis; parfois ils comptent et parfois non.

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

Addenda mathématique

Pour être complet, la définition précise de la notation big-O est la suivante: f(x) ∈ O(g(x))signifie que "f est asymptotiquement borné par const * g": en ignorant tout en dessous d'une valeur finie de x, il existe une constante telle que |f(x)| ≤ const * |g(x)|. (Les autres symboles sont les suivants: tout comme les Omoyens ≤, les Ωmoyens ≥. Il existe des variantes en minuscules: les omoyens <et les ωmoyens>.) f(x) ∈ Ɵ(g(x))Signifie les deux f(x) ∈ O(g(x))et f(x) ∈ Ω(g(x))(bornes supérieure et inférieure par g): il existe des constantes telles que f sera toujours dans la "bande" entre const1*g(x)et const2*g(x). C'est la déclaration asymptotique la plus forte que vous puissiez faire et à peu près équivalente à==. (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 n'ai jamais vu de valeurs négatives apparaître dans un contexte informatique.)

Les gens utiliseront souvent = O(...), qui est peut-être la notation «comp-sci» la plus correcte, et tout à fait légitime à utiliser; "f = O (...)" est lu "f est l'ordre ... / f est xxx délimité par ..." et est considéré comme "f est une expression dont les asymptotiques sont ...". On m'a appris à utiliser les plus rigoureux ∈ O(...). ∈signifie "est un élément de" (toujours lu comme précédemment). Dans ce cas particulier, O(N²)contient des éléments tels que { 2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} et est infiniment grand, mais il est encore un ensemble.

O et Ω ne sont pas symétriques (n = O (n²), mais n² n'est pas O (n)), mais Ɵ est symétrique, et (puisque ces relations sont toutes transitives et réflexives) Ɵ, par conséquent, est symétrique et transitif et réflexif , et partitionne donc l'ensemble de toutes les fonctions en classes d'équivalence . Une classe d'équivalence est un ensemble de choses que nous considérons comme identiques. C'est-à-dire, étant donné n'importe quelle fonction à laquelle vous pouvez penser, vous pouvez trouver un «représentant asymptotique» canonique / unique de la classe (en prenant généralement la limite ... je pense ); tout comme vous pouvez regrouper tous les nombres entiers en cotes ou en evens, vous pouvez regrouper toutes les fonctions avec Ɵ en x-ish, log (x) ^ 2-ish, etc ... en ignorant fondamentalement les termes plus petits (mais parfois vous pourriez être coincé avec fonctions plus complexes qui sont des classes distinctes en soi).

La =notation est peut-être la plus courante et est même utilisée dans des articles par des informaticiens de renommée mondiale. De plus, il arrive souvent que dans un cadre décontracté, les gens disent O(...)quand ils veulent dire Ɵ(...); c'est techniquement vrai car l'ensemble des choses Ɵ(exactlyThis)est un sous-ensemble de O(noGreaterThanThis)... et il est plus facile à taper. ;-)

EDIT: Note rapide, cela confond presque certainement la notation Big O (qui est une borne supérieure) avec la notation Theta (qui est à la fois une borne supérieure et une borne inférieure). D'après mon expérience, cela est en fait typique des discussions dans des contextes non universitaires. Toutes mes excuses pour toute confusion causée.

En une phrase: à mesure que la taille de votre travail augmente, combien de temps faut-il pour le terminer?

Évidemment, cela n'utilise que "taille" comme entrée et "temps pris" comme 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 supposerons qu'il est incroyablement rapide de les mettre en position de séchage (c'est-à-dire que l'interaction humaine est négligeable). Ce n'est pas le cas dans la vraie vie, bien sûr ...

• Utiliser une ligne de lavage à l'extérieur: en supposant que vous ayez une cour arrière infiniment grande, le lavage sèche en O (1). Peu importe ce que vous en avez, il recevra le même soleil et l'air frais, donc la taille n'affecte pas le temps de séchage.

• À l'aide d'un sèche-linge: vous mettez 10 chemises dans chaque brassée, puis elles sont terminées une heure plus tard. (Ignorez les chiffres réels ici - ils ne sont pas pertinents.) Ainsi, le séchage de 50 chemises prend environ 5 fois plus de temps que le séchage de 10 chemises.

• Tout mettre dans une armoire aérée: si nous mettons tout dans un gros tas et que nous laissons la chaleur générale le faire, il faudra beaucoup de temps pour que les chemises du milieu sèchent. Je ne voudrais pas deviner le détail, mais je pense que c'est au moins O (N ^ 2) - lorsque vous augmentez la charge de lavage, le temps de séchage augmente plus rapidement.

Un aspect important de la notation "big O" est qu'il ne dit pas quel algorithme sera plus rapide pour une taille donnée. Prenez une table de hachage (clé de chaîne, valeur entière) par rapport à un tableau de paires (chaîne, entier). Est-il plus rapide de trouver une clé dans la table de hachage ou un élément dans le tableau, basé sur une chaîne? (ie pour le tableau, "trouvez le premier élément où la partie chaîne correspond à la clé donnée.") Les tables de hachage sont généralement amorties (~ = "en moyenne") O (1) - une fois qu'elles sont configurées, cela devrait prendre environ en même temps pour trouver une entrée dans une table à 100 entrées comme dans une table à 1 000 000 entrées. Trouver un élément dans un tableau (basé sur le contenu plutôt que sur l'index) est linéaire, c'est-à-dire O (N) - en moyenne, vous allez devoir regarder la moitié des entrées.

Cela rend-il une table de hachage plus rapide qu'un tableau pour les recherches? Pas nécessairement. Si vous avez une très petite collection d'entrées, un tableau peut bien être plus rapide - vous pourrez peut-être vérifier toutes les chaînes dans le temps qu'il faut pour calculer simplement le code de hachage de celui que vous regardez. Cependant, à mesure que l'ensemble de données s'agrandit, la table de hachage finira par battre le tableau.

Big O décrit une limite supérieure du comportement de croissance d'une fonction, par exemple le temps d'exécution d'un programme, lorsque les entrées deviennent importantes.

Exemples:

• O (n): si je double la taille d'entrée, le temps d'exécution double

• O (n ² ): si la taille d'entrée double les quadruples d'exécution

• O (log n): si la taille d'entrée double, le temps d'exécution augmente d'une unité

• O (2 ⁿ ): si la taille d'entrée augmente d'une unité, le temps d'exécution double

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

La notation Big O est le plus souvent utilisée par les programmeurs comme mesure approximative du temps nécessaire à un calcul (algorithme) pour s'exprimer en fonction de la taille de l'ensemble d'entrée.

Big O est utile pour comparer la façon dont deux algorithmes vont évoluer à mesure que le nombre d'entrées augmente.

Plus précisément, la notation Big O est utilisée pour exprimer le comportement asymptotique d'une fonction. Cela signifie comment la fonction se comporte lorsqu'elle approche de l'infini.

Dans de nombreux cas, le "O" d'un algorithme tombera dans l'un des cas suivants:

• O (1) - Le temps pour terminer est le même quelle que soit la taille du jeu d'entrées. Un exemple est l'accès à un élément de tableau par index.
• O (Log N) - Le temps pour terminer augmente à peu près en ligne avec le log2 (n). Par exemple, 1024 éléments prennent environ deux fois plus de 32 éléments, car Log2 (1024) = 10 et Log2 (32) = 5. Un exemple consiste à rechercher un élément dans une arborescence de recherche binaire (BST).
• O (N) - Temps de réalisation qui évolue linéairement 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 environ deux fois plus de temps. Un exemple consiste à compter le nombre d'éléments dans une liste chaînée.
• O (N Log N) - Le temps pour terminer augmente du nombre d'éléments multiplié par le résultat de Log2 (N). Un exemple de ceci est le tri en tas et le tri rapide .
• O (N ^ 2) - Le temps pour terminer est à peu près égal au carré du nombre d'articles. Un exemple de ceci est le tri à bulles .
• O (N!) - Le temps nécessaire pour terminer est la factorielle de l'ensemble d'entrée. Un exemple de ceci est la solution de force brute du problème du voyageur de commerce .

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

Big O est juste un moyen de vous "exprimer" d'une manière courante, "Combien de temps / d'espace faut-il pour exécuter mon code?".

Vous pouvez souvent voir O (n), O (n ² ), O (nlogn) et ainsi de suite, ce ne sont que des moyens de montrer; Comment un algorithme change-t-il?

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. Imagerie que vous souhaitez rechercher un élément dans un tableau. Vous devriez regarder chaque élément et comme "Êtes-vous le bon élément / article?" dans le pire des cas, l'item est au dernier index, ce qui signifie qu'il a fallu autant de temps qu'il y a d'items dans la liste, donc pour être générique, nous disons "oh hé, n est une bonne quantité donnée de valeurs!" .

Alors vous comprendrez peut-être ce que "n ² " signifie, mais pour être encore plus précis, jouez avec la pensée que vous avez un algorithme de tri simple, le plus simple; Bubblesort. Cet algorithme doit parcourir toute la liste, pour chaque élément.

Ma liste

1. 1
2. 6
3. 3

Le flux ici serait:

• Comparez 1 et 6, lequel est le plus grand? Ok 6 est dans la bonne position, va de l'avant!
• Comparez 6 et 3, oh, 3, c'est moins! Bougeons ça, Ok la liste a changé, il faut partir du début maintenant!

Ceci est O n ² car, vous devez regarder tous les éléments de la liste, il y a des "n" éléments. Pour chaque article, vous regardez tous les articles une fois de plus, pour comparer, c'est aussi "n", donc pour chaque article, vous regardez "n" fois signifiant n * n = n ²

J'espère que c'est aussi simple que vous le souhaitez.

Mais rappelez-vous, Big O est juste un moyen de vous experser dans 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 sur un algorithme donné. Il coupe à l'os et ne donne que des informations sur la nature de mise à l'échelle d'un algorithme, en particulier la façon dont l'utilisation des ressources (temps de réflexion ou mémoire) d'un algorithme évolue en réponse à la "taille d'entrée".

Considérez la différence entre une machine à vapeur et une fusée. Ce ne sont pas simplement des variétés différentes de la même chose (comme, par exemple, un moteur Prius contre un moteur Lamborghini), mais ce sont des types de systèmes de propulsion radicalement différents, à la base. Un moteur à vapeur peut être plus rapide qu'une fusée jouet, mais aucun moteur à piston à vapeur ne pourra atteindre les vitesses d'un lanceur orbital. En effet, ces systèmes ont des caractéristiques d'échelle différentes en ce qui concerne la relation de carburant nécessaire («utilisation des ressources») pour atteindre une vitesse donnée («taille d'entrée»).

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

Prenons l'exemple du tri canonique. Le tri à bulles est O (n ² ) tandis que le tri par fusion est O (n log n). Supposons que vous ayez deux applications de tri, l'application A qui utilise le tri à bulles et l'application B qui utilise le tri par fusion, et disons que pour des tailles d'entrée d'environ 30 éléments, l'application A est 1000 fois plus rapide que l'application B au tri. Si vous n'avez jamais à trier plus de 30 éléments, il est évident que vous devriez préférer l'application A, car elle est beaucoup plus rapide à ces tailles d'entrée. Cependant, si vous constatez que vous devrez peut-être trier dix millions d'éléments, ce que vous attendez, c'est que l'application B finit en fait par des milliers de fois plus vite que l'application A dans ce cas, entièrement en raison de la façon dont chaque algorithme évolue.

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

Dans tous les cas, préférez les algorithmes plus haut dans la liste à ceux plus bas dans la liste. Cependant, le coût du passage à une classe de complexité plus coûteuse varie considérablement.

O (1):

Pas de croissance. Quelle que soit l'ampleur du problème, vous pouvez le résoudre dans le même laps de temps. Ceci est quelque peu analogue à la radiodiffusion où il faut la même quantité d'énergie pour diffuser sur une distance donnée, quel que soit le nombre de personnes qui se trouvent dans la plage de diffusion.

O (log n ):

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

O ( n ):

Le coût de résolution du problème est proportionnel à la taille du problème. Si votre problème double de taille, le coût de la solution double. Étant donné que la plupart des problèmes doivent être analysés dans l'ordinateur d'une manière ou d'une autre, comme la saisie de données, les lectures de disque ou le trafic réseau, il s'agit généralement d'un facteur de mise à l'é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 évolutif. En modifiant les hypothèses, certains algorithmes O ( n log n ) peuvent être transformés en algorithmes O ( n ) . Par exemple, la limitation de la taille des clés réduit le tri de O ( n log n ) à O ( n ) .

O ( n ² ):

Grandit comme un carré, où n est la longueur du côté d'un carré. Il s'agit du 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 coûte cher. La plupart des solutions évolutives ne peuvent pas utiliser d'algorithmes avec ce niveau de complexité sans faire de gymnastique importante. Cela s'applique généralement à toutes les autres complexités polynomiales - O ( n ^k ) - également.

O (2 ⁿ ):

N'évolue pas. Vous n'avez aucun espoir de résoudre un problème de taille non triviale. Utile pour savoir ce qu'il faut éviter et pour les experts de trouver des algorithmes approximatifs qui sont en O ( n ^k ) .

Big O est une mesure du temps / espace qu'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 / espace augmente au rythme de son entrée au carré.

etc.

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

Une explication en anglais simple de la nécessité de la notation Big-O:

Lorsque nous programmons, nous essayons de résoudre un problème. Ce que nous codons s'appelle un algorithme. La notation Big O nous permet de comparer les performances les plus défavorables de nos algorithmes de manière standardisée. Les spécifications matérielles varient dans le temps et les améliorations matérielles peuvent réduire le temps nécessaire à l'exécution des algorithmes. Mais le remplacement du matériel ne signifie pas que notre algorithme est meilleur ou amélioré au fil du temps, car notre algorithme est toujours le même. Donc, afin de nous permettre de comparer différents algorithmes, de déterminer si l'un est meilleur ou non, nous utilisons la notation Big O.

Une explication en anglais simple de ce Big O Notation:

Tous les algorithmes ne s'exécutent pas 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 du cas le plus défavorable, ou une limite supérieure du temps d'exécution lorsque n devient de plus en plus grand. Nous devons être conscients de ce que n est, car de nombreuses notations Big O le référencent.

Il est très difficile de mesurer la vitesse des logiciels, et lorsque nous essayons, les réponses peuvent être très complexes et remplies d'exceptions et de cas spéciaux. C'est un gros problème, car toutes ces exceptions et cas spéciaux sont distrayants et inutiles lorsque nous voulons comparer deux programmes différents entre eux pour savoir lequel est "le plus rapide".

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

Parce que ce sont des approximations, nous utilisons la lettre "O" (Big Oh) dans l'expression, comme convention pour signaler au lecteur que nous faisons une simplification excessive. (Et pour s'assurer que personne ne pense à tort que l'expression est en aucune façon exacte).

Si vous lisez "Oh" comme signifiant "de l'ordre de" ou "approximativement", vous ne vous tromperez pas trop. (Je pense que le choix du Big-Oh aurait pu être une tentative d'humour).

La seule chose que ces expressions "Big-Oh" essaient de faire est de décrire le ralentissement du logiciel à mesure que nous augmentons la quantité de données que le logiciel doit traiter. Si nous doublons la quantité de données à traiter, le logiciel a-t-il besoin de deux fois plus de temps pour terminer son travail? Dix fois plus longtemps? En pratique, il existe un nombre très limité d'expressions big-Oh que vous rencontrerez et dont vous devrez vous soucier:

Le bon:

• O(1) Constante : le programme prend le même temps pour s'exécuter, quelle que soit la taille de l'entrée.
• O(log n) Logarithmique : le temps d'exécution du programme n'augmente que lentement, même avec de grandes augmentations de la taille de l'entrée.

Le mauvais:

• O(n) Linéaire : l'exécution du programme augmente proportionnellement à la taille de l'entrée.
• O(n^k) Polynôme : - Le temps de traitement augmente de plus en plus vite - en tant que fonction polynomiale - à mesure que la taille de l'entrée augmente.

... et le laid:

• O(k^n) Exponentiel Le temps d'exécution du programme augmente très rapidement avec des augmentations même modérées de la taille du problème - il est seulement pratique de traiter de petits ensembles de données avec des algorithmes exponentiels.
• O(n!) Factorielle L'exécution du programme sera plus longue que vous ne pouvez vous permettre d'attendre autre chose que les jeux de données les plus petits et les plus triviaux.

Une réponse simple et directe peut être:

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

D'accord, mes 2 cents.

Big-O, est le taux d'augmentation des ressources consommées par le programme, par rapport à la taille de l'instance de problème

Ressource: pourrait être le temps total du processeur, pourrait être un espace RAM maximum. Par défaut, se réfère au temps CPU.

Disons 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;
}

problem-instance = {5,10,15} ==> problem-instance-size = 3, iterations-in-loop = 3

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

Pour une entrée de taille "n", le programme croît à la vitesse de "n" itérations dans le tableau. Par conséquent, Big-O est N exprimé en O (n)

Dites que le problème est "Trouvez 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;
      }
    }

problem-instance = {5,10,15} ==> problem-instance-size = 3, total-iterations = 3 * 3 = 9

problem-instance = {5,10,15,20,25} ==> problem-instance-size = 5, total-iterations = 5 * 5 = 25

Pour une entrée de taille "n", le programme se développe à une vitesse de "n * n" itérations dans le tableau. Donc Big-O est N ² exprimé en O (n ² )

La notation Big O est une façon de décrire la limite supérieure d'un algorithme en termes d'espace ou de temps d'exécution. Le n est le nombre d'éléments dans le problème (c'est-à-dire la taille d'un tableau, le nombre de nœuds dans une arborescence, etc.). Nous souhaitons décrire le temps d'exécution lorsque n devient grand.

Lorsque nous disons qu'un algorithme est O (f (n)), nous disons que le temps d'exécution (ou l'espace requis) par cet algorithme est toujours inférieur à certains temps constants f (n).

Dire que la recherche binaire a un temps d'exécution de O (logn) revient à dire qu'il existe une constante c que vous pouvez multiplier par log (n) qui sera toujours plus grande que le temps d'exécution de la recherche binaire. Dans ce cas, vous aurez toujours un facteur constant de comparaisons log (n).

En d'autres termes où g (n) est le temps d'exécution de votre algorithme, nous disons que g (n) = O (f (n)) lorsque g (n) <= c * f (n) lorsque n> k, où c et k sont des constantes.

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

Une telle question magnifiquement simple et courte semble au moins mériter une réponse tout aussi courte, comme un étudiant pourrait recevoir pendant le tutorat.

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

(* dans un merveilleux temps sans unité !)
(** c'est ce qui compte, car les gens en voudront toujours plus , qu'ils vivent aujourd'hui ou demain)

Eh bien, qu'est-ce qui est si merveilleux avec la notation Big O si c'est ce qu'elle 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 une constante comme la proportionnalité d' un moteur JavaScript, la vitesse d'une unité centrale de traitement, votre connexion Internet, et toutes ces choses qui deviennent rapidement devenir aussi risible démodés un modèle T . Big O se concentre sur la performance uniquement de la manière qui compte autant pour les personnes vivant dans le présent ou dans le futur.

• La notation Big O met également en lumière directement le principe le plus important de la programmation / ingénierie informatique, ce qui inspire tous les bons programmeurs à continuer de penser et de rêver: la seule façon d'obtenir des résultats au-delà de la marche lente de la technologie est d' inventer une meilleure 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 recherche une liste, article par article, à la recherche d'une clé,

• En itérant sur chaque élément de la liste, si c'est la clé, retournez True,

• Si la boucle est terminée sans trouver la clé, retournez False.

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

Pour trouver le Big-O sur la complexité du temps:

• Calculez combien de temps (en ce qui concerne la taille d'entrée) le pire des cas prend:

• Pire cas: la clé n'existe pas dans la liste.

• Temps (pire cas) = ​​4n + 1

• Temps: O (4n + 1) = O (n) | en Big-O, les constantes sont négligées

• O (n) ~ Linéaire

Il y a aussi le Big-Omega, qui représente la complexité du meilleur cas:

• Meilleur cas: la clé est le premier élément.

• Temps (meilleur cas) = ​​4

• Temps: Ω (4) = O (1) ~ Instant \ Constante

Big O

f (x) = O ( g (x)) lorsque x passe à a (par exemple, a = + ∞) signifie qu'il existe une fonction k telle que:

1. f (x) = k (x) g (x)

2. k est borné dans un voisinage de a (si a = + ∞, cela signifie qu'il y a des nombres N et M tels que pour chaque x> N, | k (x) | <M).

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

Petit o

Au fait, voici à titre de comparaison la définition du petit o.

f (x) = o ( g (x)) lorsque x va à a signifie qu'il existe une fonction k telle que:

1. f (x) = k (x) g (x)

2. k (x) passe à 0 lorsque x passe à 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 "fausse égalité": il est vrai que o (g (x)) = O (g (x)), mais faux que O (g (x)) = o (g (X)). De même, il est correct d'écrire "ln (x) = o (x) lorsque x → + ∞", mais la formule "o (x) = ln (x)" n'aurait aucun sens.

Plus d'exemples

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

• 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 Wikipedia: https://en.wikipedia.org/wiki/Big_O_notation

La notation Big O est une façon de décrire la vitesse d'exécution d'un algorithme étant donné un nombre arbitraire de paramètres d'entrée, que nous appellerons "n". Il est utile en informatique parce que différentes machines fonctionnent à des vitesses différentes, et dire simplement qu'un algorithme prend 5 secondes ne vous dit pas grand-chose car pendant que vous utilisez un système avec un processeur octo-core de 4,5 Ghz, je peux être en train d'exécuter un système vieux de 15 ans, 800 MHz, qui pourrait prendre plus de temps quel que soit l'algorithme. Ainsi, au lieu de spécifier à quelle vitesse un algorithme s'exécute en termes de temps, nous disons à quelle vitesse il s'exécute en termes de nombre de paramètres d'entrée, ou "n". En décrivant les algorithmes de cette manière, nous sommes en mesure de comparer les vitesses des algorithmes sans avoir à prendre en compte la vitesse de l'ordinateur lui-même.

Je ne suis pas sûr de contribuer davantage au sujet, mais je pensais toujours partager: j'ai trouvé une fois que ce billet de blog contenait des explications et des exemples très utiles (bien que très basiques) sur Big O:

Grâce à des exemples, cela a aidé à mettre les bases nues dans mon crâne de type écaille de tortue, donc je pense que c'est une lecture de 10 minutes pour vous diriger dans la bonne direction.

Vous voulez tout savoir sur le grand O? Moi aussi.

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

Maintenant, laissez-nous parler du travail. La plupart du temps, je n'aime pas le travail. Aimez-vous le travail? C'est peut-être le cas, mais je suis sûr que non.

Je n'aime pas aller travailler. Je n'aime pas passer du temps au travail. Si je le pouvais, j'aimerais juste jouer et faire des choses amusantes. Ressentez-vous la même chose que moi?

Maintenant, parfois, je dois aller travailler. C'est triste, mais vrai. Donc, quand je suis au travail, j'ai une règle: j'essaie de faire moins de travail. Aussi peu que possible de travail. Alors je vais jouer!

Voici donc la grande nouvelle: le grand O peut m'aider à ne pas travailler! Je peux jouer plus de temps, si je connais un gros O. Moins de travail, plus de jeu! C'est ce que le grand O m'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 bon, je dois faire ça. Alors c'est parti.

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

Alors ne faisons pas le travail. Laissez-vous et moi penser à quel point c'est difficile. Combien de travail devrais-je faire pour ajouter six chiffres?

Voyons voir. Je dois ajouter un et deux, puis ajouter cela à trois, puis ajouter cela à quatre… En tout, je compte six ajouts. Je dois faire six ajouts pour résoudre ce problème.

Voici un grand O, pour nous dire à quel point ce calcul est difficile.

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

Eh bien, je ne ferai pas le travail pour les ajouter maintenant. Mais je sais à quel point ce serait difficile. Ce serait six ajouts.

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

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

Ce serait beaucoup plus difficile? Combien de travail devrais-je encore faire? Ai-je besoin de plus ou moins d'étapes?

Eh bien, je suppose que je devrais faire dix ajouts… un pour chaque chose de un à dix. Dix est plus de six. Il faudrait que je travaille beaucoup plus pour ajouter de un à dix, de un à six!

Je ne veux pas ajouter pour l'instant. Je veux juste réfléchir à la difficulté d’ajouter autant. Et, j'espère, jouer dès que possible.

Ajouter de un à six, c'est du travail. Mais voyez-vous, pour ajouter de un à dix, c'est plus de travail?

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

Maintenant, nous devons faire un nouveau travail. Oh non. Je n'aime pas du tout ce travail.

Le nouveau travail est: ajouter toutes choses de un à n.

Attendre! Qu'est-ce que n? J'ai raté ça? Comment puis-je ajouter de un à n si vous ne me dites pas ce qu'est n?

Eh bien, je ne sais pas ce que n est. On ne m'a pas dit. Étiez-vous? Non? Tant pis. Nous ne pouvons donc pas faire le travail. Ouf.

Mais bien que nous ne fassions pas le travail maintenant, nous pouvons deviner à quel point ce serait difficile, si nous savions n. Il faudrait additionner n choses, non? Bien sûr!

Maintenant, voici grand O, et il nous dira à quel point ce travail est difficile. Il dit: ajouter toutes choses de un à N, un par un, c'est O (n). Pour ajouter toutes ces choses, [je sais que je dois ajouter n fois.] [1] C'est grand O! Il nous dit combien il est difficile de faire un certain type de travail.

Pour moi, je pense au grand O comme à un grand et lent patron. Il pense au travail, mais il ne le fait pas. Il pourrait dire: "Ce travail est rapide." Ou, il pourrait dire: "Ce travail est si lent et difficile!" Mais il ne fait pas le travail. Il regarde simplement le travail, puis il nous dit combien de temps cela pourrait prendre.

Je me soucie beaucoup du grand O. Pourquoi? Je n'aime pas travailler! Personne n'aime travailler. C'est pourquoi nous aimons tous le grand O! Il nous dit à quelle vitesse nous pouvons travailler. Il nous aide à penser à quel point le travail est difficile.

Euh oh, plus de travail. Maintenant, ne faisons pas le travail. Mais, faisons 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 du tout droits. Et maintenant ... notre travail consiste à les trier.

Ergh. Cela a l'air de faire beaucoup de travail!

Comment pouvons-nous trier ce jeu? J'ai un plan.

Je vais regarder chaque paire de cartes, paire par paire, à travers le jeu, du premier au dernier. Si la première carte d'une paire est grande et la carte suivante de cette paire est petite, je les échange. Sinon, je passe à la paire suivante, et ainsi de suite et ainsi de suite ... et bientôt, le jeu est terminé.

Une fois le jeu terminé, je demande: ai-je échangé des cartes dans cette passe? Si c'est le cas, je dois tout recommencer, par le haut.

À un moment donné, à un moment donné, il n'y aura plus de swaps, et notre sorte de jeu serait faite. Tant de travail!

Eh bien, quel serait le travail, pour trier les cartes avec ces règles?

J'ai dix cartes. Et, la plupart du temps - c'est-à-dire, si je n'ai pas beaucoup de chance - je dois parcourir tout le deck jusqu'à dix fois, avec jusqu'à dix échanges de cartes à chaque fois dans le deck.

Big O, aidez-moi!

Big O entre et dit: pour un jeu de n cartes, le trier de cette façon se fera en temps O (N au carré).

Pourquoi dit-il n au carré?

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

Maintenant, quand le grand O dit qu'il faudra du travail O (n au carré), il ne veut pas dire que n au carré ajoute, sur le nez. Cela pourrait être un peu moins, dans certains cas. Mais dans le pire des cas, il faudra près de n carrés de travail pour trier le jeu.

Maintenant, c'est là que le grand O est notre ami.

Big O le fait remarquer: lorsque n devient grand, lorsque nous trions les cartes, le travail devient BEAUCOUP PLUS DUR que l'ancien travail consistant simplement à ajouter ces choses. Comment savons-nous cela?

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

Pour les gros n, n au carré est plus grand que n.

Big O nous dit que trier les choses est plus difficile que d'ajouter des choses. O (n au carré) est supérieur à O (n) pour le grand n. Cela signifie: si n devient vraiment grand, trier un ensemble mixte de n choses DOIT prendre plus de temps que d'ajouter simplement n choses mixtes.

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

J'ai un jeu de cartes. Je les ai triés. Tu as aidé. Merci.

Existe-t-il un moyen plus rapide de trier les cartes? Le grand O peut-il nous aider?

Oui, il existe un moyen plus rapide! Il faut du temps pour apprendre, mais ça marche ... et ça marche assez vite. Vous pouvez aussi l'essayer, mais prenez votre temps à chaque étape et ne perdez pas votre place.

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

Un: je choisis une carte dans la partie du deck sur laquelle nous travaillons actuellement. Vous pouvez en choisir un pour moi si vous le souhaitez. (La première fois que nous faisons cela, «la partie du deck sur laquelle nous travaillons maintenant» est le deck entier, bien sûr.)

Deux: J'écarte le jeu sur la carte que vous avez choisie. Quel est cet écart; comment puis-je m'écarter? Bon, je vais de la carte de départ vers le bas, une par une, et je cherche une carte plus haute que la carte évasée.

Trois: je vais de la fin de la carte vers le haut, et je cherche une carte plus basse que la carte évasée.

Une fois que j'ai trouvé ces deux cartes, je les échange et continue à chercher d'autres cartes à échanger. C'est-à-dire que je reviens à la deuxième étape et que je rejoue la carte que vous avez choisie.

À un moment donné, cette boucle (de deux à trois) se terminera. Il se termine lorsque les deux moitiés de cette recherche se rencontrent sur la carte évasée. Ensuite, nous venons d'écarter le jeu avec la carte que vous avez choisie à l'étape un. Maintenant, toutes les cartes proches du début sont plus basses que la carte évasée; et les cartes proches de la fin sont plus hautes que la carte évasée. Truc cool!

Quatre (et c'est la partie amusante): J'ai maintenant deux petits decks, un plus bas que la carte évasée, et un plus haut. Je passe maintenant à la première étape, sur chaque petit deck! C'est-à-dire que je commence à partir de la première étape sur le premier petit pont, et lorsque ce travail est terminé, je commence à partir de la première étape sur le petit petit pont suivant.

Je décompose le jeu en plusieurs parties, je trie chaque partie, de plus en plus petite, et à un moment donné, je n'ai plus de travail à faire. Maintenant, cela peut sembler lent, avec toutes les règles. Mais croyez-moi, ce n'est pas lent du tout. C'est beaucoup moins de travail que la première façon de trier les choses!

Comment s'appelle ce genre? Cela s'appelle Tri rapide! Ce tri a été fait par un homme appelé CAR Hoare et il l'a appelé Tri rapide. Maintenant, le tri rapide est utilisé tout le temps!

Le tri rapide décompose les grands decks en petits. C'est-à-dire qu'il décompose les grandes tâches en petites.

Hmmm. Il y a peut-être une règle là-dedans, je pense. Pour réduire les tâches importantes, divisez-les.

Ce type est assez rapide. À quelle vitesse? Big O nous dit: ce type nécessite un travail O (n log n), dans le cas moyen.

Est-il plus ou moins rapide que le premier tri? Big O, s'il vous plaît, aidez-moi!

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

Si vous devez trier un jeu, quelle est la meilleure façon? Eh bien, vous pouvez faire ce que vous voulez, mais je choisirais le tri rapide.

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

Comment savoir que le tri rapide nécessite moins de travail? Je sais que O (n log n) est inférieur à O (n au carré). Les O sont plus petits, donc le tri rapide demande moins de travail!

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

Tu as appris tout ça avec moi! Tu es tellement intelligent! Merci beaucoup!

Maintenant que le travail est terminé, allons jouer!

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

J'ai une façon plus simple de comprendre la complexité temporelle. La métrique la plus courante pour calculer la complexité temporelle est la notation Big O. Cela supprime tous les facteurs constants afin que le temps de fonctionnement puisse être estimé par rapport à N lorsque N approche de l'infini. En général, vous pouvez le voir comme ceci:

statement;

Est constant. Le temps d'exécution de l'instruction ne changera pas par rapport à N

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

Est linéaire. Le temps de parcours de la boucle est directement proportionnel à N. Lorsque N double, il en est de même du temps de parcours.

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

Est quadratique. Le temps de fonctionnement des deux boucles est proportionnel au carré de N. Lorsque N double, le temps de fonctionnement augmente de 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 que 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 se compose de N boucles (itératives ou récursives) logarithmiques, donc l'algorithme est une combinaison de linéaire et de logarithmique.

En général, faire quelque chose avec chaque élément dans une dimension est linéaire, faire quelque chose avec chaque élément dans deux dimensions est quadratique, et diviser la zone de travail en deux est logarithmique. Il existe d'autres mesures Big O telles que cubique, exponentielle et racine carrée, mais elles ne sont pas aussi courantes. La notation Big O est décrite comme O () où est la mesure. L'algorithme de tri rapide serait décrit comme O (N * log (N)).

Remarque: rien de tout cela n'a pris en compte les meilleures, moyennes et pires mesures. Chacun aurait sa propre notation Big O. Notez également qu'il s'agit d'une explication TRÈS simpliste. Big O est le plus courant, mais c'est aussi plus complexe que je l'ai montré. Il existe également d'autres notations telles que gros oméga, petit o et gros thêta. Vous ne les rencontrerez probablement pas en dehors d'un cours d'analyse d'algorithmes.

• Voir plus sur: ici

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

Et si je commande plusieurs films Blu-ray comme Le Seigneur des anneaux, Twilight, The Dark Knight Trilogy, etc. et télécharge tous les films en ligne en même temps? Cette fois, la livraison prend encore une journée, mais le téléchargement en ligne prend 3 jours. Pour les achats en ligne, le nombre d'articles achetés (entrée) n'affecte pas le délai de livraison. La sortie est constante. Nous appelons cela O (1) .

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

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

Remarque: la 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

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

Signifie alors O( <some expression X involving n> ), en anglais simple:

Si vous n'avez pas de chance lors de l'exécution de A, cela peut prendre jusqu'à X (n) opérations.

En fait, il existe certaines fonctions (pensez-y comme des implémentations de 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 les comparant lorsque l'on parle de A et d'autres algorithmes, il est facile de classer les algorithmes en fonction du nombre d'opérations qu'ils peuvent (dans le pire des cas) nécessiter pour terminer.

En général, notre objectif sera de trouver ou de structurer un algorithme A de telle manière qu'il aura une fonction X(n)qui renvoie un nombre aussi bas que possible.

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

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

Et en plus

Les facteurs constants sont négligeables

Si vous effectuez une mise à niveau vers un ordinateur capable d'exécuter votre algorithme deux fois plus rapidement, la grande notation O ne le remarquera pas. Les améliorations constantes des facteurs sont trop petites pour être même remarquées dans l'échelle avec laquelle la grande notation O fonctionne. Notez que c'est une partie intentionnelle de la conception de la grande notation O.

Cependant, tout ce qui est "plus grand" qu'un facteur constant peut être détecté.

Lorsque vous êtes intéressé à faire des calculs dont la taille est suffisamment "grande" pour être considérée comme approximativement l'infini, la grande notation O représente approximativement le coût de 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 devriez probablement ignorer tout ce qui précède; la seule façon que je sache de rendre ces idées rigoureuses, ou de les expliquer si elles ne sont pas déjà intuitivement utiles, est de vous enseigner d'abord la grande notation O ou quelque chose de similaire. (bien que, une fois que vous aurez bien compris la notation O à l'avenir, il pourrait être utile de revoir ces idées)

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

Note très rapide:

Le O dans "Big O" fait référence à "Ordre" (ou précisément "ordre de")
afin que vous puissiez avoir son idée littéralement qu'il est utilisé pour commander quelque chose pour les comparer.

• "Big O" fait deux choses:

  1. Estime le nombre d'étapes de la méthode appliquée par votre ordinateur pour accomplir une tâche.
  2. Faciliter le processus de comparaison avec les autres afin de déterminer s'il est bon ou non?
  3. "Big O 'atteint les deux ci-dessus avec standardisé Notations.

• Il y a sept notations les plus utilisées

  1. O (1), signifie que votre ordinateur effectue une tâche avec 1étape, c'est excellent, ordonné n ° 1
  2. O (logN), signifie que votre ordinateur accomplit une tâche avec des logNétapes, c'est bien, ordonné n ° 2
  3. O (N), terminer une tâche avec des Nétapes, sa foire, commande n ° 3
  4. O (NlogN), termine une tâche par O(NlogN)étapes, ce n'est pas bon, commande n ° 4
  5. O (N ^ 2), faites une tâche avec des N^2étapes, c'est mauvais, commande n ° 5
  6. O (2 ^ N), faites une tâche avec des 2^Nétapes, c'est horrible, commande n ° 6
  7. O (N!), Faites une tâche avec des N!étapes, c'est terrible, commande n ° 7

Supposons que vous obteniez une notation O(N^2), non seulement vous êtes clair que la méthode prend N * N étapes pour accomplir une tâche, mais vous voyez aussi que ce n'est pas bon d' O(NlogN)après son classement.

Veuillez noter la commande en fin de ligne, juste pour votre meilleure compréhension. Il y a plus de 7 notations si toutes les possibilités sont envisagées.

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

De plus, Big O établit le pire des cas ou mesure les étapes de la limite supérieure.
Vous pouvez vous référer à Big-Ω (Big-Omega) pour le meilleur cas.

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

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

  ou y répondre formellement, "Big O" classe les algorithmes et standardise le processus de comparaison.

La façon la plus simple de voir les choses (en anglais simple)

Nous essayons de voir comment le nombre de paramètres d'entrée affecte le temps d'exécution d'un algorithme. Si le temps d'exécution de votre application est proportionnel au nombre de paramètres d'entrée, alors il est dit être en Big O de n.

La déclaration ci-dessus est un bon début mais pas complètement vraie.

Une explication plus précise (mathématique)

Supposer

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

Ensuite, en ce qui concerne Big O, l'approximation f (n) est considérée comme suffisamment bonne tant que la condition ci-dessous est vraie.

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

L'équation est lue comme lorsque n s'approche de l'infini, T de n, est inférieur ou égal à c fois f de n.

En grande notation O, cela s'écrit

T(n)∈O(n)

Cela se lit comme T de n est en grand O de n.

Retour à l'anglais

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

Un grand O de n signifie que mon algorithme fonctionne au moins aussi vite que cela. Vous ne pouvez pas regarder la notation Big O de votre algorithme et dire que c'est lent. Vous ne pouvez dire que son rapide.

Découvrez ceci pour un tutoriel vidéo sur Big O de UC Berkley. C'est en fait un concept simple. Si vous entendez le professeur Shewchuck (alias professeur au niveau de Dieu) l'expliquer, vous direz "Oh, c'est tout!".

J'ai trouvé une très bonne explication à propos de la grande notation O, en particulier pour quelqu'un qui n'est pas beaucoup en mathématiques.

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

La notation Big O est utilisée en informatique pour décrire les performances ou la complexité d'un algorithme. Big O décrit spécifiquement le pire des scénarios et peut être utilisé pour décrire le temps d'exécution requis ou l'espace utilisé (par exemple en mémoire ou sur disque) par un algorithme.

Quiconque a lu Programming Pearls ou tout autre livre d'informatique et n'a pas de connaissances en mathématiques aura heurté un mur lorsqu'ils auront atteint les chapitres qui mentionnent O (N log N) ou une autre syntaxe apparemment folle. J'espère que cet article vous aidera à comprendre les bases du Big O et des logarithmes.

En tant que programmeur en premier et mathématicien en second (ou peut-être troisième ou quatrième), j'ai trouvé que la meilleure façon de bien comprendre Big O était de produire quelques exemples dans le code. Ainsi, voici quelques ordres de croissance courants ainsi que des descriptions et des exemples lorsque cela est possible.

O (1)

O (1) décrit un algorithme qui s'exécutera 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;
}

SUR)

O (N) décrit un algorithme dont les performances augmenteront 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 le pire scénario de performance; une chaîne correspondante pourrait être trouvée lors de toute itération de la boucle for et la fonction retournerait tôt, mais la notation Big O supposera toujours la limite supérieure où l'algorithme effectuera le nombre maximal 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 les performances sont directement proportionnelles au carré de la taille de l'ensemble de données d'entrée. Cela est courant avec les algorithmes qui impliquent des itérations imbriquées sur l'ensemble de données. Des itérations imbriquées plus profondes entraîneront 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 avec chaque ajout à l'ensemble de données d'entrée. La courbe de croissance d'une fonction O (2 ^N ) est exponentielle - commençant très peu profondément, puis augmentant de façon météorique. Un exemple de fonction O (2 ^N ) est le calcul récursif des nombres de Fibonacci:

int Fibonacci(int number) {
    if (number <= 1) return number;

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

Logarithmes

Les logarithmes sont légèrement plus difficiles à expliquer, je vais donc utiliser un exemple courant:

La recherche binaire est une technique utilisée pour rechercher des ensembles de données triés. Il fonctionne en sélectionnant l'élément central de l'ensemble de données, essentiellement la médiane, et le compare à une valeur cible. Si les valeurs correspondent, cela renverra le succès. Si la valeur cible est supérieure à la valeur de l'élément de sonde, elle prendra la moitié supérieure de l'ensemble de données et effectuera 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 effectuera l'opération contre la moitié inférieure. Il continuera de réduire de moitié l'ensemble de données à chaque itération jusqu'à ce que la valeur soit trouvée ou jusqu'à ce qu'il ne puisse plus diviser l'ensemble de données.

Ce type d'algorithme est décrit comme O (log N). La division itérative des ensembles de données décrite dans l'exemple de recherche binaire produit une courbe de croissance qui culmine au début et s'aplatit lentement à mesure que la taille des ensembles de données augmente, par exemple, un ensemble de données d'entrée contenant 10 éléments prend une seconde pour terminer, un ensemble de données contenant 100 éléments prend deux secondes, et un ensemble de données contenant 1000 éléments prend trois secondes. Le doublement de la taille de l'ensemble de données d'entrée a peu d'effet sur sa croissance, car après une seule itération de l'algorithme, l'ensemble de données sera divisé par deux et donc à égalité avec un ensemble de données d'entrée de moitié. Cela rend les algorithmes comme la recherche binaire extrêmement efficaces lorsqu'il s'agit de grands ensembles de données.

Il s'agit d'une explication très simplifiée, mais j'espère qu'elle couvre les détails les plus importants.

Supposons que votre algorithme traitant le problème dépend de certains «facteurs», par exemple, faisons-le N et X.

Selon N et X, votre algorithme nécessitera certaines opérations, par exemple dans le pire des cas, ce sont des 3(N^2) + log(X)opérations.

Étant donné que Big-O ne se soucie pas trop du facteur constant (aka 3), le Big-O de votre algorithme est O(N^2 + log(X)). Il traduit fondamentalement `` la quantité d'opérations dont votre algorithme a besoin pour les pires cas avec cela ''.

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 devez créer une fonction pour additionner les nombres de 0 à N. Vous obtenez f (x) et votre ami arrive avec g (x). Les deux fonctions ont le même résultat, mais un algorithme différent. Afin de comparer objectivement l'efficacité des algorithmes, nous utilisons la notation Big-O .

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

3 points clés à retenir:

1. Comparez la vitesse à laquelle le runtime se développe PAS comparez les temps d'exécution exacts (dépend du matériel)
2. Seulement concerné par le temps d'exécution croît par rapport à l'entrée (n)
3. Comme n devient arbitrairement grand, concentrez-vous sur les termes qui croîtront le plus rapidement car n devient grand (pensez à l'infini) Analyse asymptotique AKA

Complexité de l'espace: outre la complexité du temps, nous nous soucions également de la complexité de l'espace (combien de mémoire / d'espace un algorithme utilise). Au lieu de vérifier l'heure des opérations, nous vérifions la taille de l'allocation de mémoire.