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


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


4529
2018-01-28 11:10


origine


Réponses:


Note rapide, ceci est presque certainement déroutant Big O notation (qui est une limite supérieure) avec la notation Theta (qui est une limite de deux côtés). D'après mon expérience, c'est en fait typique des discussions dans des contextes non académiques. Toutes mes excuses pour toute confusion causée.


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

Big O Analysis

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 quelques mots importants et délibérément choisis dans cette phrase:

  • relatif: vous ne pouvez comparer que des pommes à des 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 faire 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 en fonction des opérations de comparaison (en comparant deux nœuds pour déterminer leur ordre relatif). Cela suppose que la comparaison est coûteuse. Mais que se passe-t-il si la comparaison est bon marché, mais l'échange est coûteux? 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 en trier un million? La complexité dans ce cas est une mesure relative à autre chose.

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

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

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

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

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

Supposons que l'addition de ces nombres soit l'opération la plus coûteuse de cet algorithme. Il va de soi que pour ajouter ces deux nombres ensemble, nous devons additionner 6 chiffres (et peut-être porter un 7ème). Si nous ajoutons deux nombres de 100 chiffres ensemble, nous devons faire 100 additions. Si nous ajoutons deux 10 000 chiffres, nous devons faire 10 000 ajouts.

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

La soustraction est similaire (sauf que vous pourriez avoir besoin d'emprunter à la place de carry).

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

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

Comme l'algorithme s'échelonne avec n-au carré, c'est Sur2) ou complexité quadratique. C'est le bon moment pour introduire un autre concept important:

Nous nous soucions uniquement de la partie la plus importante de la complexité.

Les astucieux ont peut-être réalisé que nous pourrions exprimer le nombre d'opérations comme: n2 + 2n. Mais comme vous l'avez vu dans notre exemple avec deux chiffres d'un million de chiffres chacun, le second 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'entre eux est à 4 chiffres et l'autre à 6 chiffres, nous n'avons que 24 multiplications. Pourtant, nous calculons le pire scénario pour ce «n», c'est-à-dire lorsque les deux sont des nombres à 6 chiffres. Par conséquent, la notation Big-O concerne le scénario le plus défavorable d'un algorithme.

L'annuaire téléphonique

Le meilleur exemple que je peux penser est le livre de téléphone, normalement appelé les pages blanches ou similaire, mais cela va varier d'un pays à l'autre. Mais je parle de celui qui énumère les gens par nom de famille et ensuite les initiales ou le prénom, éventuellement l'adresse et ensuite les numéros 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 contenant 1 000 000 de noms, que feriez-vous? Ignorant le fait que vous pourriez 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, prendre les 500 000th et comparez-le à "Smith". S'il se trouve que c'est "Smith, John", nous avons vraiment eu de la chance. Beaucoup plus probable est que "John Smith" sera avant ou après ce nom. Si c'est après nous divisons alors la moitié de l'annuaire en deux et répétez. Si c'est avant, nous divisons la première moitié du répertoire en deux et répétez. Etc.

C'est ce qu'on appelle un recherche binaire et est utilisé chaque jour dans la programmation si vous le réalisez ou non.

Donc, si vous voulez trouver un nom dans un annuaire téléphonique d'un million de noms, vous pouvez trouver un nom en faisant cela 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 maximum).
  • Pour 7 il faut au plus 3.
  • Pour 15 cela prend 4.
  • ...
  • Pour 1.000.000, il en faut 20.

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

En termes de Big-O, c'est O (log n) ou complexité logarithmique. Maintenant, le logarithme en question pourrait être ln (base e), logdix, log2 ou une autre base. Peu importe, c'est toujours O (log n) comme O (2n2) et O (100n2) sont toujours les deux O (n2).

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

  • Meilleur cas: Dans la recherche de l'annuaire téléphonique, le meilleur des cas est que nous trouvons le nom dans une comparaison. C'est O (1) ou complexité constante;
  • Cas attendu: Comme discuté ci-dessus, c'est O (log n); et
  • Pire cas: C'est aussi O (log n).

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

Retour à l'annuaire téléphonique.

Que faire si vous avez un numéro de téléphone et que vous voulez trouver un nom? La police a un annuaire inversé, mais de telles consultations 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, génial, sinon, passez à la suivante. Vous devez le faire de cette façon parce que le répertoire est non ordonné (par numéro de téléphone de toute façon).

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

  • Meilleur cas: O (1);
  • Cas attendu: O (n) (pour 500 000); et
  • Pire cas: O (n) (pour 1 000 000).

Le vendeur ambulant

C'est un problème assez célèbre 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 tour le plus court qui visite chaque ville.

Cela semble simple? Réfléchis encore.

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

  • A → B → C
  • A → C → B
  • B → C → A
  • B → A → C
  • C → A → B
  • C → B → A

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

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

  • Prenez ceci à 4 villes et vous avez (iirc) 12 possibilités.
  • Avec 5 c'est 60.
  • 6 devient 360.

Ceci est une fonction d'une opération mathématique appelée factoriel. 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 × 1064

Donc, le Big-O du problème de voyageur de commerce est Sur!) ou complexité factorielle ou combinatoire.

Au moment où vous arrivez à 200 villes, il ne reste pas 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 Surune) est dit avoir complexité polynomiale ou est soluble dans Temps polynomial.

O (n), O (n2) 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 est un excellent exemple. Il est difficile de trouver deux facteurs premiers d'un très grand nombre. Si ce n'était pas le cas, nous ne pourrions pas utiliser les systèmes à clé publique que nous utilisons.

Quoi qu'il en soit, c'est tout pour mon explication de l'O Big (révisée).


6089
2018-01-28 11:18



Il montre comment un algorithme évolue.

Sur2): connu comme Complexité quadratique

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

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

Sur): connu comme Complexité linéaire

  • 1 article: 1 seconde
  • 10 éléments: 10 secondes
  • 100 articles: 100 secondes

Cette fois, le nombre d'objets 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 comme Complexité constante

  • 1 article: 1 seconde
  • 10 articles: 1 seconde
  • 100 articles: 1 seconde

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

O (log n): connu comme Complexité logarithmique

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

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

C'est l'essentiel. Ils réduisent les maths de sorte qu'il ne soit pas exactement n2 ou tout ce qu'ils disent c'est, mais ce sera le facteur dominant dans la mise à l'échelle.


662
2018-01-28 11:28



La notation Big-O (appelée aussi notation "croissance asymptotique") est quelles fonctions "ressemblent" quand vous ignorez les facteurs constants et les choses près de l'origine. Nous l'utilisons pour parler de comment échelle de chose.


Notions de base

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

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

La notation big-O ne se soucie pas des facteurs constants: la fonction 9x² est dit de "grandir exactement comme" 10x². Ni grand-O asymptotique notation se soucient de non-asymptotique des trucs ("trucs proches de l'origine" ou "que se passe-t-il quand la taille du problème est petite"): la fonction 10x² est dit de "grandir 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 en considérant des échelles de plus en plus grandes; leur contribution devient minime et non pertinente. (Voir la section exemple.)

En d'autres termes, tout est dans le rapport comme vous allez à l'infini. Si vous divisez le temps réel qu'il faut par le O(...), vous aurez un facteur constant dans la limite des grandes entrées. Intuitivement, cela a du sens: les fonctions «se ressemblent» si vous pouvez multiplier une pour obtenir l'autre. C'est, quand on dit ...

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 "assez grandes" N (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 y a beaucoup de 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 des facteurs constants pour savoir pourquoi ils n'ont généralement pas d'importance). Vous pouvez également penser à l'équation ci-dessus comme une limite, en disant "Dans le pire des cas, le temps qu'il faudra ne sera jamais pire qu'environ N*log(N), dans un facteur de 2,5 (un facteur constant dont nous nous soucions peu)".

En général, O(...) est le plus utile parce que nous nous soucions souvent du pire des cas. Si f(x) représente quelque chose de "mauvais" comme le processeur ou l'utilisation de la mémoire, alors "f(x) ∈ O(upperbound)" veux dire "upperbound est le pire scénario 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 du temps de traitement et de la mémoire. Vous pouvez l'utiliser pour discuter de l'asymptotique de tout ce qui a un sens, par exemple:

  • le nombre de poignées de main éventuellement entre N les gens à une fête (Ɵ(N²), Plus précisément N(N-1)/2, mais ce qui compte c'est que ça "balance comme" )
  • nombre probabiliste attendu de personnes ayant vu un peu de marketing viral en fonction du temps
  • la façon dont la latence du site Web évolue avec le nombre d'unités de traitement dans un processeur ou une unité graphique ou un cluster d'ordinateurs
  • comment les échelles de production de chaleur sur les processeurs meurent en fonction du nombre de transistors, de la tension, etc.
  • combien de temps un algorithme doit-il exécuter, en fonction de la taille de l'entrée
  • combien d'espace un algorithme doit exécuter, en fonction de la taille de l'entrée

Exemple

Pour l'exemple de poignée de main ci-dessus, tout le monde dans une pièce secoue 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 (Chacun des N secoue les mains de N-1 autres personnes, mais ce double compte les poignées de mains donc divise par 2):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article.  adjacency matrix

Cependant, pour un très grand nombre de personnes, le terme linéaire N est réduit et contribue effectivement 0 au ratio (dans le graphique: la fraction des cases vides sur la diagonale sur les cases totales devient plus petite à 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 "grandit comme N²".

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

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

(digression temporaire de "plain english" :) Si vous vouliez vous le prouver, vous pourriez effectuer une algèbre simple sur le ratio pour le diviser en plusieurs termes (limsignifie "considéré dans la limite de", ignorez simplement si vous ne l'avez pas vu, c'est juste une notation pour "et N est vraiment très grand"):

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

tl; dr: Le nombre de poignées de main 'ressemble beaucoup à' x² pour les grandes valeurs, que si nous écrivions le ratio # handshakes / x², le fait que nous n'en ayons pas besoin exactement Les poignées de main x2 n'apparaîtraient même pas dans la décimale pour un temps arbitrairement grand.

par exemple. pour x = 1million, ratio # handshakes / x²: 0.499999 ...


Construire l'intuition

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

"Pour assez grand inputize = N, peu importe ce que le facteur constant est, si je double la taille d'entrée


362
2017-07-08 04:46



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

En une phrase: Comme 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. Bien assumer il est incroyablement rapide de les amener 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 ...

  • Utilisation d'une ligne de lavage à l'extérieur: en supposant que vous avez une arrière-cour infiniment grande, le lavage sèche en O (1) fois. Quel que soit le résultat, le soleil et l'air frais sont identiques, de sorte que la taille n'affecte pas le temps de séchage.

  • Utilisation d'un sèche-linge: vous mettez 10 chemises dans chaque chargement, puis elles sont faites une heure plus tard. (Ignorer les chiffres réels ici - ils ne sont pas pertinents.) Donc, le séchage de 50 chemises prend sur 5 fois plus de temps que le séchage de 10 chemises.

  • Tout mettre dans un placard aéré: Si nous mettons tout dans un grand tas et que nous laissons la chaleur générale le faire, il faudra beaucoup de temps pour que les chemises du milieu se dessèchent. Je ne voudrais pas deviner le détail, mais je suppose que c'est au moins O (N ^ 2) - à mesure que 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 pas dire quel algorithme sera le plus rapide pour une taille donnée. Prenez une hashtable (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? (pour le tableau, "trouver le premier élément où la partie de chaîne correspond à la clé donnée.") Les tables de hachage sont généralement amorties (~ = "en moyenne") O (1) - une fois configurées, cela devrait prendre environ en même temps pour trouver une entrée dans une table de 100 entrées comme dans une table d'entrée de 1 000 000. 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 devrez regarder la moitié des entrées.

Est-ce que cela rend une hashtable 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 être plus rapide - vous pourrez peut-être vérifier toutes les chaînes dans le temps qu'il faut pour calculer le code de hachage de celui que vous regardez. Au fur et à mesure que l'ensemble de données augmente, la table de hachage finit par battre le tableau.


237
2018-01-28 11:16



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

Exemples:

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

  • Sur2): 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'un

  • O (2n): Si la taille d'entrée augmente de un, 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.


120
2018-01-28 11:23



La notation Big O est le plus souvent utilisée par les programmeurs comme une mesure approximative de la durée d'un calcul (algorithme) pour compléter exprimé en fonction de la taille de l'ensemble d'entrée.

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

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

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

  • O (1) - L'heure de fin est la même quelle que soit la taille de l'ensemble d'entrée. Un exemple est l'accès à un élément de tableau par index.
  • O (journal N) - Le temps de terminer augmente à peu près en ligne avec le log2 (n). Par exemple 1024 éléments prend environ deux fois plus de 32 éléments, car Log2 (1024) = 10 et Log2 (32) = 5. Un exemple est de trouver un élément dans un arbre de recherche binaire (BST).
  • SUR) - Temps pour terminer qui échelles linéairement avec la taille de l'ensemble d'entrée. En d'autres termes, si vous doublez le nombre d'éléments dans le jeu d'entrée, l'algorithme prend environ deux fois plus de temps. Un exemple consiste à compter le nombre d'éléments dans une liste liée.
  • O (N Journal N) - Le temps de terminer augmente par le nombre d'éléments multiplié par le résultat de Log2 (N). Un exemple de ceci est type de tas et tri rapide.
  • O (N ^ 2) - L'heure de fin est approximativement égale au carré du nombre d'éléments. Un exemple de ceci est tri à bulles.
  • SUR!) - L'heure de fin est la factorielle de l'ensemble d'entrée. Un exemple de ceci est le problème de voyageur de transport solution de force brute.

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.


97
2017-09-05 16:31



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

Vous pouvez souvent voir O (n), O (n2), O (nlogn) et ainsi de suite, tout cela n'est que des façons de montrer; Comment un algorithme change-t-il?

O (n) signifie que Big O est n, et maintenant vous pourriez penser, "Qu'est-ce que n !?" Eh bien "n" est la quantité d'éléments. Imaging vous voulez 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, on dit "oh hey, n est une juste quantité de valeurs!" .

Alors vous pourriez comprendre ce que "n2"signifie, mais pour être encore plus spécifique, jouez avec la pensée que vous avez un algorithme de tri simple, le plus simple," bubbleort "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, ce qui est le plus grand? Ok 6 est dans la bonne position, aller de l'avant!
  • Comparez 6 et 3, oh, 3 est moins! Passons à cela, Ok la liste a changé, nous devons commencer dès le début maintenant!

C'est O n2 parce que, 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 ce qui signifie n * n = n2

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

Mais rappelez-vous, Big O est juste un moyen de vous expirer à la manière du temps et de l'espace.


77
2018-01-28 11:14



Big O décrit la nature d'é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 donne seulement des informations sur la nature d'échelle d'un algorithme, en particulier comment l'utilisation de la ressource (penser le temps ou la mémoire) d'un algorithme évolue en fonction de la "taille d'entrée".

Considérez la différence entre une machine à vapeur et une fusée. Ils ne sont pas simplement des variétés différentes de la même chose (comme, par exemple, un moteur Prius vs un moteur Lamborghini), mais ils sont radicalement différents types de systèmes de propulsion, à leur noyau. Une machine à vapeur peut être plus rapide qu'une fusée jouet, mais aucun moteur à pistons à 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 entre le carburant requis («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 allant jusqu'à un billion. Considérez cela pour un moment. Le rapport entre la vitesse nécessaire pour se rendre à la Lune et la vitesse de marche de l'homme est inférieur à 10 000: 1, ce qui est absolument minime par rapport à la plage des tailles d'entrée auxquelles le logiciel peut faire face. Et parce que le logiciel peut faire face à une plage astronomique dans les tailles d'entrée, il est possible que la complexité de Big O d'un algorithme, sa nature d'échelle fondamentale, l'emporte sur tous les détails d'implémentation.

Considérons l'exemple de tri canonique. Le tri par bulles est O (n2) alors que merge-sort est O (n log n). Supposons que vous ayez deux applications de tri, l'application A qui utilise le tri par bulles et l'application B qui utilise le tri par fusion, et disons que pour les 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 trouvez que vous pourriez avoir à trier dix millions d'éléments, vous vous attendez à ce que l'application B finisse par être mille fois plus rapide que l'application A dans ce cas, entièrement à cause de la façon dont chaque algorithme évolue.


52
2018-01-28 13:12



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

Dans tous les cas, préférez les algorithmes plus haut dans la liste à ceux situés 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 la taille du problème, vous pouvez le résoudre dans le même laps de temps. Ceci est quelque peu analogue à la diffusion 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 portée de diffusion.

O (journal n):

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

O (n):

Le coût de la résolution du problème est proportionnel à la taille du problème. Si votre problème double de taille, le coût de la solution double. Comme 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, la lecture de disque ou le trafic réseau, il s'agit généralement d'un facteur d'échelle abordable.

O (n bûche 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 peaufinant certaines hypothèses O (n bûche n) les algorithmes peuvent être transformés en O (n) algorithmes. Par exemple, limiter la taille des touches réduit le tri de O (n bûche n) à O (n).

O (n2):

Grandit comme un carré, où n est la longueur du côté d'un carré. C'est le même taux de croissance que l'effet réseau, où tout le monde dans un réseau peut connaître tous les autres membres du réseau. La croissance est chère. La plupart des solutions évolutives ne peuvent pas utiliser des algorithmes avec ce niveau de complexité sans faire de la gymnastique significative. Ceci s'applique généralement à toutes les autres complexités polynomiales - O (nk) - ainsi que.

O (2n):

Ne pas échelle. Vous n'avez aucun espoir de résoudre un problème de taille non triviale. Utile pour savoir quoi éviter, et pour les experts de trouver des algorithmes approximatifs qui sont en O (nk).


35
2018-01-27 23:09