Complexité d'une fonction

[Pyrobyte]

Bonjour à tous,

je cherche à trouver la complexité de la fonction f(n)=2n²+5n+10 en terme de O et Ω

Pour info, ou rappel des définitions, je ne sais pas^^

Pour ce genre de fonction polynomiale, on a en général le plus haut degré qui fait office de complexité et donc il s'agit d'un théta de n² ici mais j'aimerais pouvoir le prouver.


Bref, f(n) est en θ(g) si f(n) est à la fois O(g) et Ω(g)

f(n) est O(g) si on peut écrire pour un c et un n_0 : f(x)<=cg(n)
f(n) est Ω(g) si on peut écrire pour un c et un n_0 : f(x)>=cg(n)


J'ai déjà fait la preuve pour O(n²)

Pour c=3 et g(n)=n²
2n² +5n +10 <= 3n²
<=> 0 <= 2²-5n-10

Ici on se ramène donc à une bête équation du second degré, on calcule le discriminant qui vaut 65.
Et on trouve dans les racines positives environ 13/2

On en déduit donc que pour c=2 et n_0 > 7 on a bien un O(n²)


Je cherche maintenant à prouver Ω(n²)

Le résultat étant que ça fonctionne pour tout n avec c=0 ou 1 ou 2.
Mais je n'arrive pas à retrouver ce résultat par le calcul.

J'ai posé

2n² +5n +10 >= cn²

En prenant c=2

<=> 5n+10 >= 0
n >= (-2)

Ce résultat confirme ce que je dosi trouver, ça fonctionne pour tout n entier positifs mais...comment prouver que cela ne marche que pour c qui vaut 0 ou 1 ou 2.

Je peux faire les 3 cas un par un bien sûr, mais...ça ne m'ass pas l'air très propre...s'il y en avait des dizaines je ne vais pas tous les calculer...je me dis qu'il y a une méthode pour retrouver directement ce résultat.


Merci pour votre aide précieuse !

[zygomatique]

salut

on a évidemment ... à partir d'un certain rang ...

[Ben314]

Salut,
Et je rajouterais que ça serait pas con de réellement connaitre les définitions en question :

f(n) est O(g) si il existe (*) un c strictement positif et un n_0 tels que, pour tout n supérieur à n_0, on ait : f(n)<=cg(n)
f(n) est Ω(g) si il existe (*) un c strictement positif et un n_0 tels que, pour tout n supérieur à n_0, on ait : f(n)>=cg(n)

Et ça serait pas con aussi de préciser que ces définitions, écrites telles quelle ne sont valables que pour des foncions f et g positives (à partir d'un certain rang).
Par exemple, bien que -n²<1xn pour tout n, ben on a pas -n²=O(n).

(*) Ca fait franchement très con de formuler un truc pareil en utilisant l'expression "on peut écrire que". Si on me demande si "je peut écrire" que 2+2=3, j'ai aucune hésitation : bien sur que je peut l'écrire, je viens même de le faire...

Ce résultat confirme ce que je dois trouver, ça fonctionne pour tout n entier positifs mais...comment prouver que cela ne marche que pour c qui vaut 0 ou 1 ou 2.

Donc ici, le "c=0" est nul est non avenu et la question "je fait comment avec toutes ces valeur de c qui marchent ?", ben tu relit la définition (écrite correctement...) : ce qu'il faut que tu montre, c'est qu'il existe au moins un c tel que... donc si tu en trouve UN qui marche, ben c'est fini, et tu as rien à f.. de savoir s'il y en a d'autres ou pas.