Bonjour, 

Je trouve facilement la complexité de mes algorithmes, mais je ne sais jamais si je dois la noter en O de quelque chose ou en theta de quelques chose. 

Je n'arrive pas à savoir si c'est en rapport avec le pire et le meilleur des cas. En gros si quelqu'un pouvait me donner la différence entre O et theta. 

J'ai compris l'histoire de : f est dominée par g, f = O(g) s'il existe n0 et c tels que pour tout n > n0 , on ait f(n) ≤ c g(n) 

f et g sont du même ordre de grandeur, f = theta(g) s'il existe n0 , c1 et c2 tels que pour tout n > n0 , on ait c1 g(n) ≤ f(n) ≤ c2 g(n)

mais je ne vois pas comment l'appliquer pour un algorithme. 

Ma question est donc juste de savoir quand on a un algorithme, que l'on a définit si il est en n2 ou  log2n ou n etc... comment sait t-on si les complexités sont à écrire en O ou theta. 

Je sais pas si tout est claire dans ma question, mais merci pour vos réponses. 

Marion 

Bonjour,

La plupart du temps on note la complexité avec les O(f).

• Si f est un theta(g), alors f est un O(g).
• Si tu as un O(g) alors tu as l'assurance que dans le pire cas, ton algorithme s'exécutera en un temps g (fois la constante).
• Si tu as un theta(g), tu as aussi l'assurance (malheureusement) que ton programme ne s'exécutera pas plus rapidement qu'un temps g (fois la constante c_1).

Pour certains algos, on a parfois seulement l'assurance sur la borne supérieure (ou plus généralement on ne calcule pas la borne inférieure même si elle peut être intéressante). Par exemple, disons qu'on cherche un algo qui nous trouve le minimum d'une liste d'entiers naturels. On a assez facilement un algorithme en O(n) qui est aussi en theta(n) (on parcourt toute la liste). Mais on pourrait faire un algorithme on s'arrête dès qu'on voit un zéro dans la liste. Ceci fait qu'on pourrait s'arrêter à la première case parcourue. On est donc toujours en O(n), mais on n'est pas en theta(n).

-
Edité par yo@n97one 13 janvier 2019 à 18:42:35