Quelle définition du taux de croissance asymptotique devrions-nous enseigner?

35

Quand nous suivons les manuels standard, ou la tradition, la plupart d' entre nous enseignent la définition suivante de la notation grand-Oh dans les premières conférences d'une classe d'algorithmes:

f=O(g) iff (c>0)(n00)(nn0)(f(n)cg(n)).
Peut-être donnons-nous même la liste complète avec tous ses quantificateurs:
  1. f=o(g) iff (c>0)(n00)(nn0)(f(n)cg(n))
  2. f=O(g) iff (c>0)(n00)(nn0)(f(n)cg(n))
  3. f=Θ(g) iff (c>0)(d>0)(n00)(nn0)(dg(n)f(n)cg(n))
  4. f=Ω(g) iff (d>0)(n00)(nn0)(f(n)dg(n))
  5. .f=ω(g) iff (d>0)(n00)(nn0)(f(n)dg(n))

Cependant, étant donné que ces définitions ne sont pas faciles à utiliser pour prouver des choses simples, telles que ,plupart d'nous déplacer rapidement pour introduire le "truc de la limite":5nlog4n+nlogn=o(n10/9)

  1. si lim n f ( n ) / g ( n ) existe et vaut 0 ,f=o(g)limnf(n)/g(n)0
  2. si lim n f ( n ) / g ( n ) existe et n'a pas de + ,f=O(g)limnf(n)/g(n)+
  3. si lim n f ( n ) / g ( n ) existe et est ni 0 ni + ,f=Θ(g)limnf(n)/g(n)0+
  4. si lim n f ( n ) / g ( n ) existe et est pas 0 ,f=Ω(g)limnf(n)/g(n)0
  5. si lim n f ( n ) / g ( n ) existe et est + .f=ω(g)limnf(n)/g(n)+

Ma question est:

Serait - ce une grande perte pour l' enseignement d' une classe d'algorithmes de premier cycle à prendre les conditions limites que les définitions de , O , thetav , Ohm et co ? En tout cas, c’est ce que nous finissons tous par utiliser et il me semble assez clair que l’omission des définitions de quantificateur facilite la vie de tout le monde.oOΘΩω

Je serais intéressé de savoir si vous avez rencontré un cas naturel convaincant où les définitions standard sont réellement requises et, dans le cas contraire, si vous avez un argument convaincant pour garder les définitions c , n 0 standard de toute façon.c,n0c,n0

slimton
la source
1
Le tag devrait vraiment être "enseignement", mais je n’ai trouvé aucun tag associé et je n’ai pas le droit de créer de nouveaux tags.
slimton
1
Cela absorbe les quantificateurs dans la définition des limites epsilon-delta. Mon seul souci est que de nombreux étudiants en CS n'ont pas pris d'analyse et que, par conséquent, leur compréhension des limites est essentiellement mécanique. Pour leur permettre de calculer rapidement, cependant, c'est une évidence.
Per Vognsen
6
Notez que vos deux définitions de O () ne sont pas équivalentes (la même mise en garde s'applique à () et à Ω ()). Considérons le cas où f (n) = 2n pour n pair et f (n) = 1 pour n impair. Est-ce que f (n) = O (n)? Je préfère utiliser limsup au lieu de lim pour pouvoir dire f (n) = (n) dans ce cas (bien qu'aucune de vos définitions ne le permette). Mais cela peut être ma préférence personnelle (et même une pratique non standard), et je n'ai jamais enseigné de cours.
Tsuyoshi Ito
2
@Tsuyoshi: Je pensais que le but de "l'astuce limite" était que c'était une condition suffisante mais non nécessaire pour . (Pour o ( ), il est également nécessaire.) Le contre-exemple de fonction oscillante n'a pas de limite. O()o()
András Salamon le
1
Ne devriez-vous pas remplacer le symbole par dans chaque définition et propriété? J'ai trouvé l'utilisation de = très dérangeante en tant qu'étudiante. ==
Jeremy

Réponses:

13

Je préfère enseigner la définition originale avec des quantificateurs.

OMI, les humains ont généralement du mal à comprendre les formules et les définitions avec plus de deux alternances de quantificateurs directement. L'introduction de nouveaux quantificateurs peut clarifier le sens de la définition. Ici, les deux derniers quantificateurs signifient simplement "pour tout n suffisamment grand", l'introduction de ce type de quantification peut aider.

Les images que je dessine pour expliquer ces concepts correspondent mieux aux versions des quantificateurs.

Je pense que la simplification des limites est utile pour les étudiants en ingénierie qui ne sont intéressés que par le calcul du taux de croissance, mais ne sera pas aussi utile pour les étudiants en informatique. En fait, utiliser cette simplification peut causer plus de tort que de bien.

Cette idée est similaire à la suggestion d'utiliser les règles de calcul des dérivées (polynômes, exponentiation, ..., règle de chaîne, ...) à la place de la définition epsilon-delta de ce principe, qui n'est pas une bonne idée.

Kaveh
la source
La notion de domination éventuelle est également utile: ssi \ esits m n > m f ( n ) < g ( n ) . Maintenant , f O ( g ) si et seulement si il existe c > 0 r f ( x ) « c g ( x ) . f(x)g(x)\esitsmn>mf(n)<g(n)fO(g)c>0f(x)cg(x)
Kaveh
9

Edit: révision majeure dans la révision 3.

Comme je n’ai jamais enseigné de cours, je ne pense pas pouvoir affirmer ce que nous devrions enseigner de manière convaincante. Néanmoins, voici ce que j'ai pensé à ce sujet.

Il existe des exemples naturels dans lesquels «l’astuce limite» telle qu’elle est écrite ne peut être appliquée. Par exemple, supposons que vous implémentiez un "vecteur de longueur variable" (comme le vecteur <T> en C ++) en utilisant un tableau de longueur fixe doublant la taille (en d'autres termes, chaque fois que vous êtes sur le point de dépasser la taille du tableau, vous réallouez le tableau deux fois plus grand que maintenant et copiez tous les éléments). La taille S ( n ) du tableau lorsque nous stockons n éléments dans le vecteur est la plus petite puissance de 2 supérieure ou égale à n . Nous voulons dire que S ( n ) = O ( n ), mais l’utilisation de «l’astuce limite» telle qu’elle est écrite dans la définition ne nous permettrait pas de le faire car S ( n) / n oscille de manière dense dans la plage [1,2). La même chose s'applique à Ω () et à ().

De manière assez distincte, lorsque nous utilisons ces notations pour décrire la complexité d’un algorithme, je pense que votre définition de Ω () est parfois gênante (bien que je suppose que cette définition soit commune). Il est plus pratique de définir que f ( n ) = Ω ( g ( n )) si et seulement si limsup f ( n ) / g ( n )> 0. C’est parce que certains problèmes sont triviaux pour une infinité de valeurs de n ( comme le problème d’usinage parfait sur un graphique avec un nombre impair n de sommets). La même chose s'applique à Θ () et à ().

Par conséquent, j'estime personnellement que les définitions suivantes sont les plus pratiques à utiliser pour décrire la complexité d'un algorithme: pour les fonctions f , g : → > 0 ,

  • f ( n ) = o ( g ( n )) si et seulement si limsup f ( n ) / g ( n ) = 0. (Ceci équivaut à lim f ( n ) / g ( n ) = 0)
  • f ( n ) = O ( g ( n )) si et seulement si limsup f ( n ) / g ( n ) <∞.
  • f ( n ) = Θ ( g ( n )) si et seulement si 0 <limsup f ( n ) / g ( n ) <.
  • f ( n ) = Ω ( g ( n )) si et seulement si limsup f ( n ) / g ( n )> 0. (Ceci est équivalent à ce que f ( n ) n'est pas o ( g ( n )).)
  • f ( n ) = ω ( g ( n )) si et seulement si limsup f ( n ) / g ( n ) =. (Ceci est équivalent à ce que f ( n ) n'est pas O ( g ( n )).)

ou équivalent,

  • f ( n ) = o ( g ( n )) si et seulement si pour tout c > 0, pour n suffisamment grand , f ( n ) ≤ cg ( n ).
  • f ( n ) = O ( g ( n )) si et seulement si pour certains c > 0, pour n suffisamment grand , f ( n ) ≤ cg ( n ).
  • f ( n ) = Θ ( g ( n )) si et seulement si f ( n ) = O ( g ( n )) et f ( n ) = Ω ( g ( n )).
  • f ( n ) = Ω ( g ( n )) si et seulement si pour certains d > 0, pour un nombre infini de n , f ( n ) ≥ dg ( n ).
  • f ( n ) = ω ( g ( n )) si et seulement si pour tout d > 0, pour un nombre infini de n , f ( n ) ≥ dg ( n ).

Mais je ne sais pas s'il s'agit d'une pratique courante ou non. Aussi, je ne sais pas si cela convient à l'enseignement. Le problème est que nous voulons parfois définir Ω () avec liminf à la place (comme vous l'avez fait dans la première définition). Par exemple, lorsque nous disons «La probabilité d'erreur de cet algorithme randomisé est 2 Ω ( n ) », nous ne voulons pas dire que la probabilité d'erreur est petite de façon exponentielle simplement pour une infinité de n !

Tsuyoshi Ito
la source
J'utilise également les définitions de limsup, mais pour les étudiants qui n'ont pas vu limsup (presque toutes), je dois développer des quantificateurs explicites de toute façon.
Jeffε
@JeffE: Je conviens que la plupart des étudiants n'ont pas vu limsup. Si nous utilisons les définitions de limsup, nous devons utiliser des quantificateurs à la place en classe.
Tsuyoshi Ito le
2
limsuplimlimnn
Actually, are there any natural examples for algorithms where the running time does oscillate?
Heinrich Apfelmus
2
@Heinrich: I already mentioned the running time of an algorithm to find a perfect matching of a graph on n vertices, but does it count as a natural example? I added another example where the running time does not oscillate but f(n)/g(n) oscillates. The example speaks about space complexity, but the time complexity of the same example has the same property.
Tsuyoshi Ito
8

Using limits is a bit confusing since (1) its a more complicated notion (2) it doesn't capture f=O(g) nicely (as we can see in the discussion above). I usually talk about functions from the Natural (strictly positive) numbers to the Natural numbers (which suffices for running times), skip the little-o stuff, and then the definition is concise and appropriate for 1st year undergrads:

Dfn: f=O(g) if for some C for all n we have that f(n)<=C*g(n)

Noam
la source
1
First I did not like this definition because stating “all n” obscures the important fact that the O() notation only cares about the behavior of the functions for large n. However, no matter which definition we choose, I guess that we should explain this fact together with the definition. Thinking that way, stating this simple definition seems quite good.
Tsuyoshi Ito
While this captures the essence, I dislike that if f(n)=n for all n, g(n)=0 for all n up to N0, and g(n)=f(n)+1 otherwise, then f=O(g) but this definition fails to capture this relationship. So one has to add some handwaving about functions that are well-behaved in some sense.
András Salamon
2
The point of talking about functions whose range is the Natural numbers (not including 0) is exactly not to fall into problems with g(n)=0.
Noam
1
@Warren Victor Shoup in his book on Computational Number Theory uses the notation len(a) instead of loga in running time analysis, which I found neat.
Srivatsan Narayanan
1
@Warren (continued) This is how he explains it: "In expressing the running times of algorithms in terms of an input a, we generally prefer to write len(a) rather than loga. One reason is esthetic: writing len(a) stresses the fact that the running time is a function of the bit length of a. Another reason is technical: for big-O estimates involving functions on an arbitrary domain, the appropriate inequalities should hold throughout the domain, and for this reason, it is very inconvenient to use functions, like log, which vanish or are undefined on some input."
Srivatsan Narayanan
5

When I took basic courses, we were given the c,n0 thing as definition and the other stuff as theorem.

I think the first one is more natural for many people that think discrete rather than continuous, that is most computer scientists (in my experience). It also fits the way we usually talk about those things better: "There is a polynomial function of degree 3 that is an upper bound for this f up to a constant factor."

Edit: You can get even closer to this way of speaking if you use this definition: fO(g):⇔c,d>0n0:f(n)cg(n)+d (Note that d=f(n0) connects this definition with the one usually given)

The limit stuff is pretty useful for calculating complexity classes, that is with pen and paper.

In any case, I think it is very useful for students to learn that there is a wealth of (hopefully) equivalent definitions. They should be able to realize that and pick out differences in case of nonequivalent definitions.

Raphael
la source
4

Having studied these concepts only a few years ago, they were not the hardest ones to grasp for my class (as opposed to concepts like induction, or contra positives). Limits and limsups are only more "intuitive" for those familiar with calculus in my opinion. But students with such a math grounding will have set-theoretic background anyway, so that they can process discrete qualifiers.

Also, more importantly, remember that ultimately your students will go on (hopefully) to read other cs theory textbooks, and perhaps even research papers one day. As such, it is better for them to be comfortable with standard notation in the field, even if it was not ideally conceived initially. There is no harm giving them alternate definitions as well, once they've assimilated the standard ones.

Amir
la source
3

For an interesting take on the issue, look at Don Knuth's nicely written letter "Calculus via O notation". He advocates the reverse view that calculus should be taught via the 'A', 'O' and 'o' notations.

Note: He uses the "A" notation as a preliminary step in defining the standard "O" notation. A quantity x is A of y (i.e., x=A(y)), if |x|y. In particular, it makes sense to say 100 is A(200).

Srivatsan Narayanan
la source
1
  1. Tsuyoshi Ito's definitions don't look quite right. For little-omega and big-omega the definitions should use liminf, not limsup. The definition of big-theta needs both a lower-bound on liminf and an upper-bound on limsup.

  2. One definition of f(n)=O(g(n)) is that there exists another function f'(n) >= f(n) such that lim f'(n)/g(n) < infinity.

  3. Why are newbies allowed to post answers but not make comments?

Warren Schudy
la source
1
As for item 1, I mean limsup in all cases, and the reason is explained in the second paragraph of my answer.
Tsuyoshi Ito
it's a spam blocking mechanism unfortunately.
Suresh Venkat
Aso, you can use latex in your answers.
Suresh Venkat
1

First, I try to develop in students some intuition, before showing equations.

  • "Merge-sort vs Insertion-Sort" is good starting point.

Then, later... I try to show both ways. Students, that relies more on intuition prefer

f=O(g) iff (c>0)(n00)(nn0)(f(n)cg(n)).
while those who relies more on math, equasions, algebra etc. , they prefer "limn" definitions.

Another aspect is that, it heavily depends on concrete studies' program. IMHO depending on previous subjects one of definitions will be more suitable - while IMHO still it is good idea to show both and accept both types of solutions.

Grzegorz Wierzowiecki
la source