Histoire de grand O

[bsangoku]

Bonjour,

Je voulais savoir si cette affirmation est vraie:
O(h)^2=O(h^2)

Merci d'avance et bonne journée!!!

[ev85]

Bonjour,

Je voulais savoir si cette affirmation est vraie:
O(h)^2=O(h^2)

Merci d'avance et bonne journée!!!

Et tu as réfléchi à ta question ?

[Sylviel]

f(h)=O(h) signifie que f(h)=h*g(h) avec g bornée. (et g tends vers 0 pour o(h) ). Déduis en le reste.

[Elerinna]

Bonjour,

Je voulais savoir si cette affirmation est vraie:
O(h)^2=O(h^2)

Merci d'avance et bonne journée!!!

La variante: ou t.q. et . Substitue g par et

On appelle la notation de Landeau puis la notation de Hardy équivalente (un cours).

[Judoboy]

Il a dit grand tau, pas petit tau.

[Elerinna]

Il a dit grand tau, pas petit tau.

Formellement la définition est issue d'une question sur la différence entre Grand O et petit o en maths :

Soit f et deux fonctions numériques définies sur un intervalle ouvert contenant ([url=([URL=http://www.math-info.univ-paris5.fr/~avner/MC1/L1_S1/cours/dl/node11.html]voir les sources ici[/url]).

On dit que au voisinage de si et seulement si il existe et tels que

c'est à dire si ne s'annule pas:

On dit que au voisinage de si et seulement si pour tout il existe tel que

c'est à dire si ne s'annule pas:

Autrement dit:

au voisinage de signifie que tend vers quand tend vers
au voisinage de , c'est dire que est borné sur un voisinage de

Comme une fonction ayant une limite en est bornée sur un voisinage de , petit o implique grand O.

La notation petit o dénote le caractère négligeable d'une fonction par rapport à une autre.
La notation grand O dénote le caractère dominé d'une fonction par rapport à une autre.

[Sylviel]

Certes, et la définition que tu as donné à 11h27 est celle de petit o, pas de grand O.

[Elerinna]

Certes, et la définition que tu as donné à 11h27 est celle de petit o, pas de grand O.

Oui, la définition de est un petit o comparé à . (la police 2 du bas tau contre la 6 du haut tau ^^).

Au fait, en guise d'application, une complexité algorithmique qui définit celle d'un problème de décision est en grand O.