Big O Question sur un algorithme avec (n ^ 2 + n) / 2 taux de croissance

Je pose cette question parce que je suis confus sur un aspect concernant la notation O grand.

J'utilise le livre, Structures de données et abstractions avec Java de Frank Carrano. Dans le chapitre sur "l'efficacité des algorithmes", il montre l'algorithme suivant:

int sum = 0, i = 1, j = 1
for (i = 1 to n) {
    for (j = 1 to i)
        sum = sum + 1
}

Il décrit initialement cet algorithme comme ayant un taux de croissance de ^{(n 2  + n)} / ₂ . Ce qui semble intuitif.

Cependant, il est alors indiqué que ^{(n 2  + n)} / ₂ se comporte comme n ² lorsque n est grand. Dans le même paragraphe , il déclare ^{(n 2  + n)} / ₂ se comporte aussi beaucoup comme ^{n 2} / ₂ . Il l'utilise pour classer l'algorithme ci-dessus comme O (n ² ) .

Je reçois que ^{(n 2  + n)} / ₂ est similaire à ^{n 2} / ₂ parce que le pourcentage sage, n fait peu de différence. Ce que je ne comprends pas, c'est pourquoi ^{(n 2  + n)} / ₂ et n ² sont similaires, quand n est grand.

Par exemple, si n = 1 000 000 :

(n^2 + n) / 2 =  500000500000 (5.000005e+11)
(n^2) / 2     =  500000000000 (5e+11)
(n^2)         = 1000000000000 (1e+12)

Ce dernier n'est pas du tout similaire. En fait, bien évidemment, c'est deux fois plus que celui du milieu. Alors, comment Frank Carrano peut-il dire qu'ils sont similaires? En outre, comment l'algorithme est-il classé comme O (n ² ) . En regardant cette boucle intérieure, je dirais que c'était n ² + ⁿ / ₂

Lors du calcul de la complexité Big-O d'un algorithme, l'élément affiché est le facteur qui contribue le plus à l'augmentation du temps d'exécution si le nombre d'éléments sur lesquels vous exécutez l'algorithme augmente.

Si vous avez un algorithme avec une complexité de (n^2 + n)/2et que vous doublez le nombre d'éléments, alors la constante 2n'affecte pas l'augmentation du temps d'exécution, le terme nprovoque un doublement du temps d'exécution et le terme n^2provoque une multiplication par quatre de l'exécution temps.
Comme le n^2terme a la plus grande contribution, la complexité Big-O est O(n^2).

La définition est que

f(n) = O(g(n))

s'il existe une constante C> 0 telle que, pour tout n supérieur à certains n_0, on ait

|f(n)| <= C * |g(n)|

Ceci est clairement vrai pour f (n) = n ^ 2 et g (n) = 1/2 n ^ 2, où la constante C doit être 2. Il est également facile de voir que c'est vrai pour f (n) = n ^ 2 et g (n) = 1/2 (n ^ 2 + n).

Lorsque vous parlez de complexité, vous ne vous intéressez qu'aux changements de facteurs temporels en fonction du nombre d'éléments ( n).

En tant que tel, vous pouvez supprimer tout facteur constant (comme 2ici).

Cela vous laisse avec O(n^2 + n).

Maintenant, pour une taille raisonnable, nle produit, c'est-à-dire n * nsera beaucoup plus gros que juste n, c'est la raison pour laquelle vous êtes également autorisé à ignorer cette partie, ce qui vous laisse en effet avec une complexité finale de O(n^2).

C'est vrai, pour les petits nombres, il y aura une différence significative, mais cela devient plus marginalement plus vous ngrossissez.

Ce n'est pas que "(n² + n) / 2 se comporte comme n² quand n est grand", c'est que (n² + n) / 2 croît comme n² lorsque n augmente .

Par exemple, lorsque n passe de 1 000 à 1 000 000

(n² + n) / 2  increases from  500500 to  500000500000
(n²) / 2      increases from  500000 to  500000000000
(n²)          increases from 1000000 to 1000000000000

De même, lorsque n passe de 1 000 000 à 1 000 000 000

(n² + n) / 2  increases from  500000500000 to  500000000500000000
(n²) / 2      increases from  500000000000 to  500000000000000000
(n²)          increases from 1000000000000 to 1000000000000000000

Ils se développent de la même manière, c'est ce dont parle Big O Notation.

Si vous tracez (n² + n) / 2 et n² / 2 sur Wolfram Alpha , ils sont tellement similaires qu'ils sont difficiles à distinguer par n = 100. Si vous tracez les trois sur Wolfram Alpha , vous voyez deux lignes séparées par un facteur constant de 2.

Il semble que vous ayez besoin de travailler un peu plus sur la grande notation O. À quel point cette notation est pratique, elle est très trompeuse en raison de l'utilisation d'un signe égal, qui n'est pas utilisé ici pour désigner l'égalité des fonctions.

Comme vous le savez, cette notation exprime une comparaison asymptotique des fonctions, et écrire f = O (g) signifie que f (n) croît au plus aussi vite que g (n) que n va à l'infini. Une façon simple de traduire cela est de dire que la fonction f / g est bornée. Mais bien sûr, nous devons prendre soin des endroits où g est nul et nous nous retrouvons avec la définition plus robuste que vous pouvez lire presque partout .

Cette notation s'avère très pratique pour l'informatique - c'est pourquoi elle est si répandue - mais elle doit être manipulée avec précaution car le signe égal que nous y voyons ne dénote pas une égalité de fonctions . C'est un peu comme dire que 2 = 5 mod 3 n'implique pas que 2 = 5 et si vous aimez l'algèbre, vous pouvez réellement comprendre la grande notation O comme quelque chose de modulo d'égalité.

Maintenant, pour revenir à votre question spécifique, il est totalement inutile de calculer quelques valeurs numériques et de les comparer: si grand soit un million, il ne tient pas compte du comportement asymptotique. Il serait plus utile de tracer le rapport des fonctions f (n) = n (n-1) / 2 et g (n) = n² - mais dans ce cas particulier, nous pouvons facilement voir que f (n) / g (n) est inférieur à 1/2 si n> 0, ce qui implique que f = O (g) .

Pour améliorer votre compréhension de la notation, vous devez

• Travaillez avec une définition claire, pas une impression floue basée sur des choses similaires - comme vous venez de le ressentir, une telle impression floue ne fonctionne pas bien.

• Prenez le temps de trouver des exemples en détail. Si vous travaillez aussi peu que cinq exemples en une semaine, cela suffira à améliorer votre confiance. C'est un effort qui en vaut vraiment la peine.

Note latérale algébrique Si A est l'algèbre de toutes les fonctions Ν → Ν et C la sous-algèbre des fonctions bornées, étant donné une fonction f l'ensemble des fonctions appartenant à O (f) est un sous- module C de A , et les règles de calcul sur le grand La notation O décrit simplement comment A fonctionne sur ces sous-modules. Ainsi, l'égalité que nous voyons est une égalité de sous- modules C de A , ce n'est qu'un autre type de module.

Je pense que vous comprenez mal ce que signifie la grande notation O.

Lorsque vous voyez O (N ^ 2), cela signifie essentiellement: lorsque le problème devient 10 fois plus important, le temps de le résoudre sera: 10 ^ 2 = 100 fois plus grand.

Frappons 1000 et 10000 dans votre équation: 1000: (1000 ^ 2 + 1000) / 2 = 500500 10000: (10000 ^ 2 + 10000) / 2 = 50005000

50005000/500500 = 99,91

Ainsi, alors que le N est devenu 10 fois plus grand, les solutions sont devenues 100 fois plus grandes. D'où il se comporte: O (N ^ 2)

si n était un 1,000,000alors

(n^2 + n) / 2  =  500000500000  (5.00001E+11)
(n^2) / 2      =  500000000000  (5E+11)
(n^2)          = 1000000000000  (1E+12)

1000000000000.00 quoi?

Bien que la complexité nous donne un moyen de prédire un coût réel (secondes ou octets selon que nous parlons de complexité temporelle ou d'espace), elle ne nous donne pas un certain nombre de secondes, ni aucune autre unité particulière.

Cela nous donne une certaine proportion.

Si un algorithme doit faire quelque chose n² fois, alors il faudra n² × c pour une valeur de c qui est le temps que prend chaque itération.

Si un algorithme doit faire quelque chose n² ÷ 2 fois, alors il faudra n² × c pour une valeur de c qui est deux fois plus longue que chaque itération.

De toute façon, le temps pris est toujours proportionnel à n².

Maintenant, ces facteurs constants ne sont pas quelque chose que nous pouvons simplement ignorer; en effet, vous pouvez avoir le cas où un algorithme avec une complexité O (n²) fait mieux qu'un algorithme avec une complexité O (n), car si nous travaillons sur un petit nombre d'éléments, l'impact des facteurs de consentement est plus grand et peut submerger d'autres préoccupations . (En effet, même O (n!) Est identique à O (1) pour des valeurs suffisamment faibles de n).

Mais ce n'est pas ce dont la complexité nous parle.

En pratique, il existe plusieurs façons d'améliorer les performances d'un algorithme:

1. Améliorez l'efficacité de chaque itération: O (n²) s'exécute toujours en n² × c secondes, mais c est plus petit.
2. Réduisez le nombre de cas vus: O (n²) s'exécute toujours en n² × c secondes, mais n est plus petit.
3. Remplacez l'algorithme par un qui a les mêmes résultats, mais une complexité moindre: par exemple, si nous pouvions remplacer quelque chose O (n²) par quelque chose O (n log n) et donc passer de n² × c₀ secondes à (n log n) × c₁ secondes .

Ou pour voir les choses d'une autre manière, nous avons pris f(n)×cquelques secondes et vous pouvez améliorer les performances en réduisant c, en réduisant nou en réduisant ce qui fretourne pour une donnée n.

Le premier que nous pouvons faire par quelques micro-opts à l'intérieur d'une boucle, ou en utilisant un meilleur matériel. Cela donnera toujours une amélioration.

La seconde, nous pouvons le faire en identifiant peut-être un cas où nous pouvons court-circuiter l'algorithme avant que tout soit examiné, ou filtrer certaines données qui ne seront pas significatives. Cela ne donnera pas d'amélioration si le coût de cette opération l'emporte sur le gain, mais ce sera généralement une amélioration plus importante que dans le premier cas, en particulier avec un grand n.

Le troisième, nous pouvons le faire en utilisant entièrement un algorithme différent. Un exemple classique serait de remplacer un tri à bulles par un tri rapide. Avec un petit nombre d'éléments, nous avons peut-être aggravé les choses (si c₁ est supérieur à c₀), mais cela permet généralement les gains les plus importants, en particulier avec un très grand n.

Dans la pratique, les mesures de complexité nous permettent de raisonner sur les différences entre les algorithmes précisément parce qu'elles ignorent la question de savoir comment la réduction de n ou de c aidera, de se concentrer sur l'examen f()

Facteur constant

Le point de la grande notation O est que vous pouvez choisir un facteur constant arbitrairement grand pour que O (fonction (n)) soit toujours plus grand que la fonction C * (n). Si l'algorithme A est un milliard de fois plus lent que l'algorithme B, alors ils ont la même complexité O, tant que cette différence n'augmente pas lorsque n augmente arbitrairement.

Supposons un facteur constant de 1000000 pour illustrer le concept - c'est un million de fois plus grand que nécessaire, mais cela illustre le fait qu'ils sont considérés comme non pertinents.

(n ^ 2 + n) / 2 "s'inscrit à l'intérieur" O (n ^ 2) car pour tout n, quelle que soit sa taille, (n ^ 2 + n) / 2 <1000000 * n ^ 2.

(n ^ 2 + n) / 2 "ne correspond pas" à un ensemble plus petit, par exemple O (n) car pour certaines valeurs (n ^ 2 + n) / 2> 1000000 * n.

Les facteurs constants peuvent être arbitrairement grands - un algorithme avec un temps d'exécution de n années a une complexité O (n) qui est "meilleure" qu'un algorithme avec un temps d'exécution de n * log (n) microsecondes.

Big-O est tout au sujet de la «complexité» d'un algorithme. Si vous avez deux algorithmes et que l'un prend n^2*kquelques secondes pour s'exécuter et l'autre prend n^2*jquelques secondes pour s'exécuter, alors vous pouvez discuter de celui qui est le meilleur, et vous pourriez être en mesure de faire des optimisations intéressantes pour essayer d'affecter kou j, mais les deux ces algorithmes sont très lents comparés à un algorithme qui prend n*mpour fonctionner. Peu importe la taille des constantes kou j, pour une entrée suffisamment grande, l' n*malgorithme gagnera toujours, même s'il mest assez grand.

Nous appelons donc les deux premiers algorithmes O(n^2), et nous appelons le second O(n). Il divise bien le monde en classes d'algorithmes. C'est à cela que sert le big-O. C'est comme diviser les véhicules en voitures, camions et bus, etc. besoin de mettre 12 personnes en un, alors c'est un argument plutôt insensé. :)