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

16

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) / 2 . Ce qui semble intuitif.

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

Je reçois que (n 2  + n) / 2 est similaire à n 2 / 2 parce que le pourcentage sage, n fait peu de différence. Ce que je ne comprends pas, c'est pourquoi (n 2  + n) / 2 et n 2 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 2 ) . En regardant cette boucle intérieure, je dirais que c'était n 2 + n / 2

Andrew S
la source
Si vous êtes intéressé, j'ai donné une réponse pour trois boucles imbriquées avec vérification du diagramme d'arbre d'exécution Un puzzle lié aux boucles imbriquées
Grijesh Chauhan
1
Fondamentalement, l'idée est qu'à mesure que la fonction ngrandit, les fonctions «n ^ 2» et votre fonction se comportent de la même manière, il y a une diffidence constante dans leur taux de croissance. Si vous avez une expression complexe, la fonction qui grandit plus vite domine.
AK_
1
@ MichaelT: Je ne pense pas que ce soit un double de cette question, car l'autre est simplement une question de mauvais comptage. Il s'agit d'une question plus subtile sur la raison pour laquelle les termes moindres (spécifiquement, multiplicateurs constants et polynômes de degré inférieur) sont ignorés. Le questionneur ici comprend apparemment déjà la question soulevée dans l'autre question, et une réponse suffisante pour cette question ne répondra pas à celle-ci.
sdenham

Réponses:

38

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

Bart van Ingen Schenau
la source
2
J'aime ça, ça devient un peu plus clair.
Andrew S
7
C'est très ondulé à la main. Pourrait être vrai ou pourrait être faux. Si vous pouvez faire un peu de maths, voyez l'une des réponses ci-dessous.
usr
2
Ce raisonnement est trop vague: cela signifierait que nous pourrions conclure que O(n * log n) = O(n), ce qui n'est pas vrai.
cfh
Ce n'est peut-être pas la réponse la plus précise ou la plus sémantiquement correcte, mais ce qui est important ici, c'est que cela m'a amené à commencer à comprendre le point central et je pense que c'était le but de l'auteur. C'est délibérément vague car les détails peuvent souvent détourner l'attention des principes fondamentaux. Il est important de voir le bois pour les arbres.
Andrew S
Bart parlait vraiment de termes, pas de facteurs. Comprenant cela, nous ne pouvons pas conclure cela O(n * log n) = O(n). Je pense que cela donne une bonne explication de la justification de la définition.
Mark Foskey
10

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

cfh
la source
4
"S'il existe des constantes C> 0 telles que, pour tout n," devrait être "S'il existe des constantes C, n_0 telles que, pour toutes n> n_0,"
Taemyr
@Taemyr: Tant que la fonction gn'est pas nulle, cela n'est en fait pas nécessaire, car vous pouvez toujours augmenter la constante C pour que la déclaration soit vraie pour les nombreuses premières n_0 valeurs finies.
cfh
Non, tant que nous regardons des fonctions, il n'y a pas un nombre fini de valeurs potentielles n_0.
Taemyr
@Taemyr: n_0 est un nombre fini. Choisissez C = max {f (i) / g (i): i = 1, ..., n_0}, puis l'instruction tiendra toujours pour les premières n_0 valeurs, comme vous pouvez facilement le vérifier.
cfh
Dans CS, cela est moins préoccupant car n est généralement la taille d'entrée, et donc discret. Dans ce cas, on peut choisir C tel que n_0 = 1 fonctionne. Mais la définition formelle est toute n supérieure à un certain seuil, ce qui élimine beaucoup de tergiversations dans l'application de la définition.
Taemyr
6

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.

Mario
la source
Quelle doit être la taille de n pour que la différence devienne marginale? Aussi, pourquoi le / 2 est-il supprimé, son existence réduit de moitié la valeur?
Andrew S
6
@AndrewS Parce que Big O Notation parle de croissance. La division par 2 n'est pas pertinente en dehors du contexte des repères et des horodatages, car elle ne modifie finalement pas le taux de croissance. Le plus gros composant, cependant, le fait et c'est tout ce que vous gardez.
Neil
2
@Niel, brillant si clair. J'aimerais que les livres le disent comme ça. Parfois, je pense que les auteurs savent trop qu'ils oublient que les simples mortels ne possèdent pas leurs connaissances fonctionnelles et qu'ils ne mettent donc pas en évidence des points importants, mais plutôt les enterrent dans une description mathématique formelle ou omettent le tout ensemble en croyant que cela est implicite.
Andrew S
J'aimerais pouvoir voter plus d'une fois cette réponse! @Neil, vous devriez écrire les livres de Big O.
Tersosauros
3

Ce n'est pas que "(n² + n) / 2 se comporte comme n² quand n est grand", c'est que (n² + n) / 2 croît commelorsque 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.

ShadSterling
la source
C'est bien, ça me le rend très clair. Merci d'avoir répondu.
Andrew S
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.

Michael Le Barbier Grünewald
la source
1
Cet article Wikipedia est difficile à suivre après le premier petit morceau. Il a été écrit pour des mathématiciens accomplis par un mathématicien accompli et n'est pas le genre de texte d'introduction que j'attendrais d'un article encyclopédique. Merci pour votre perspicacité bien que tout soit bon.
Andrew S
Vous surestimez le niveau dans le texte de Wikipédia! :) Ce n'est pas si bien écrit, c'est sûr. Graham, Knuth et Patashnik ont ​​écrit un joli livre «Concrete Mathematics» pour les étudiants en CS. Vous pouvez également essayer «l'art de la programmation informatique» ou un livre de théorie des nombres écrit dans les années 50 (Hardy & Wright, Rose) car ils ciblent généralement les élèves du secondaire. Vous n'avez pas besoin de lire le livre complet, si vous en choisissez un, juste la partie asymptotique! Mais avant de décider combien vous devez comprendre. :)
Michael Le Barbier Grünewald
1

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)

Pieter B
la source
1

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

Jon Hanna
la source
"O (n!) Est identique à O (1) pour des valeurs suffisamment basses de n" est tout simplement faux. Il doit y avoir une meilleure façon d'expliquer que "quand il nest maintenu suffisamment bas, Big-O n'a pas d'importance".
Ben Voigt
@BenVoigt Je n'en ai pas encore rencontré un avec le même impact rhétorique que celui-ci lors de ma première lecture; ce n'est pas à l'origine le mien, je l'ai volé à Eric Lippert, qui peut l'avoir créé ou l'avoir pris à quelqu'un d'autre. Bien sûr, il fait référence à des blagues telles que "π est égal à 3 pour les petites valeurs de π et les grandes valeurs de 3" qui est plus ancien encore.
Jon Hanna
0

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.

Peter est
la source
0

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é. :)

Jason Walton
la source