Pratiquons donc l'idée de comparer deux polynômes,
par exemple, et de décider s'
ils appartiennent ou non à la même classe.
Donc, nous définissons la classe elle-même.
Pour ce faire, nous commençons par
l'idée de la notation Big-o,
qui est parfois notée est
soulignée o dans le texte écrit à la main.
La procédure ici est la suivante.
Fondamentalement, suppose que nous avons deux de nos fonctions
comme x carré et 5x carré moins 100x.
Nous parlons, d'une manière ou d'une autre, de
la limite supérieure d'
une fonction par rapport à une autre.
Fondamentalement, cela signifie qu'une fonction n'est pas
plus grande que dans un nombre fixe
de fois que l'autre.
En d'autres termes, nous devons écrire ici une inégalité.
Fondamentalement, supposons que nous avons
un voisinage d'un point donné, un, par exemple.
Nous appelons une fonction
Big-o d'une autre fonction dans ce voisinage.
S' il y a une constante,
constante positive, C comme la relation, la
valeur absolue de la relation des
fonctions f et g ne dépasse pas
cette valeur c. Prenons donc,
par exemple, notre cas.
Nous avons x carré,
par exemple, appelons-le f est x carré,
g est 5x carré moins
100x et je suppose que x approche de l'infini.
Donc, ce que nous allons faire, nous allons dire, c'
est qu'une fonction est plus grande que l'
autre dans un quartier de l'infini.
Nous devons écrire quelque chose
comme la valeur absolue de f
est inférieure ou égale à une
constante multipliée par la valeur absolue de g, d'accord ?
En d'autres termes, x au carré inférieur ou supérieur à une
constante multipliée par Epsilon
[inaudible] 5x au carré moins 100x.
Il est assez facile de comprendre ce qui
est en fait bon pour nous ici.
Par exemple, commençons par
la constante c, égale à un.
Eh bien, il est évident que c'est le cas,
parce que si on suppose que c est égal à un.
Ainsi, nous obtenons x carré d'un côté et
5x carrés moins 100x de l'autre côté.
Si nous soustrayons x carré des
deux côtés, ainsi, nous obtenons des fonctions,
qui sont clairement positives à partir d'un certain point,
parce que nous regardons
une fonction parabolique avec positive.
Mon coefficient, donc, il
y a une racine et après cette racine,
nous n'avons que des valeurs positives.
Ainsi, cette inégalité tient et un.
F est Big-o vers G,
c'était un exemple.
Un code soutient facilement que si nous avons besoin
d'échanger cette fonction qui est toujours valable,
juste parce que au lieu d'écrire c est égal à un.
Essayons de faire cette interprétation ici.
Donc, fondamentalement, nous devons prouver quelque chose, comme ça ici.
Donc, pour faire chacun,
nous devons considérer un autre c néant,
petit, mais un grand.
Donc fondamentalement, nous commençons par comme c équivaut à cinq.
Ensuite, nous obtenons un bon résultat ici.
Mais ce n'est pas toujours le cas, parce que, par exemple,
regardons un cas plus intéressant.
Par exemple, qu'est-ce que [inaudible] fonctionne,
sinus de x et x, à
mesure que x approche de zéro ? On sait quoi ?
Ils sont fondamentalement équivalents comme on devrait s'y attendre,
que le sinus x est fondamentalement un Big-O de x.
C'est assez facile, parce que
la valeur absolue du sinus x, comme nous l'avons dit,
alors que nous parlions de notre deuxième limite importante,
est maintenant supérieure au modèle x,
parce que la valeur absolue de x
est en fait la zone du secteur,
et le sinus de x est la zone du triangle respectivement.
Donc, avec cela, nous comptons qu'
en utilisant une constante c égale à un,
nous obtenons cela absolument juste.
Mais que se passe-t-il si nous substituons un point d'intérêt
à zéro, disons l'infini ?
Tout d'abord, les idées que le sinus de x
est big-o vers x,
tient toujours à ce point même, parce que fondamentalement, le
sinus de x n'est pas supérieur à un et x est le plus grand.
Comme vous pouvez l'imaginer, x approche de l'infini.
Ainsi, cette inégalité tient toujours,
par exemple, pour la même constante égale à une.
Mais si nous le changeons,
si nous changeons deux fonctions,
alors nous obtenons 380,
[inaudible] ici, parce que les sinus x
et x ne sont pas liés dans les temps.
Parce que sine x est toujours, désolé,
je vous ai dit que nous
devons échanger des fonctions et ne l'avons pas fait.
Donc c'est une grande tromperie ici.
C' est moins trompeur.
Donc x est Big-O à partir du sinus de x.
donc fondamentalement, le
sinus de x est délimité par un et moins un et x est non limité.
Ainsi, si nous avons essayé de trouver l'idée
que x devrait être inférieure à une certaine constante,
multipliée par le sinus de x et nous disons que cette
constante, par exemple, 10.000.
Alors, quelle est l'erreur ?
Ensuite, nous pouvons par exemple,
prendre x plus grand que deux, puisque n,
cette équation, nous allons presque
certainement tomber et
ce n'est extrêmement pas le cas.
Ce n'est pas juste. Donc, quand
nous parlons de la notation Big-o,
vous devez toujours considérer l'ordre ici.
Quelle fonction, en ce qui concerne quelle fonction ? C'est Big-o ?