Problème avec les O

[xanderj]

Hello le forum,

on a vu les O l'an dernier et on a vu que sa permet de classer les algos. On a vu que O(log n) c'est mieux que O(nlogn) qui est mieux O(n) etc ... log c'est mieux lineaire mieux que polynomial mieux qu'exponentiel. mais dans le cours je vien de voir que O(3^n) c'est pire que O(2^n) pourtant c'est de l'exponentiel et je comprend pas. Vous pouver m'aidé a comprendre stp

[kwariz]

Bonjour,

tu trouves ça plus choquant que O(n³) «est pire» que O(n²) pourtant O(n²) comme O(n³) «c'est du polynomial» ?

[Aleph69]

Salut,

il faudrait savoir ce que tu entends par "mieux que" et "pire que". Formellement, ça veut dire quoi? A mon avis, ton problème vient du fait que tu as une vision beaucoup trop qualitative de la notation O.

[pseudocode]

Envoyé par xanderj

on a vu les O l'an dernier et on a vu que sa permet de classer les algos. On a vu que O(log n) c'est mieux que O(nlogn) qui est mieux O(n) etc ... log c'est mieux lineaire mieux que polynomial mieux qu'exponentiel. mais dans le cours je vien de voir que O(3^n) c'est pire que O(2^n) pourtant c'est de l'exponentiel et je comprend pas. Vous pouver m'aidé a comprendre stp

Je n'aime pas trop la terminologie "mieux/pire", je préfère "est dominé par/ domine". voila ce qu'on pourrait dire:

• f=O(g) <==> f est dominé par g <==> limite{ f/g } = 0
• g=O(f) <==> f domine g <==> limite{ f/g } = +oo
• f~g <==> f est équivalent à g <==> limite{ f/g } = Constante non-nulle

lim { 3^n / 2^n } = lim { (3/2)^n } = +oo
<==> 3^n domine 2^n
<==> 2^n = O(3^n)

[kwariz]

Envoyé par pseudocode

Je n'aime pas trop la terminologie "mieux/pire", je préfère "est dominé par/ domine". voila ce qu'on pourrait dire:

• f=O(g) <==> f est dominé par g <==> limite{ f/g } = 0
• g=O(f) <==> f domine g <==> limite{ f/g } = +oo
• f~g <==> f est équivalent à g <==> limite{ f/g } = Constante non-nulle

lim { 3^n / 2^n } = lim { (3/2)^n } = +oo
<==> 3^n domine 2^n
<==> 2^n = O(3^n)

Bonjour,

Les limites aident mais l'équivalence n'a lieue que quand la limite vaut 1. Si la limite converge vers une constante non nulle on peut juste dire que f∈O(g) et g∈O(f). Cela pourrait se résumer en :

• lim f/g = ∞ alors g∈O(f) et f∉O(g)
• lim f/g = a>0 alors g∈O(f) et f∈O(g)
• lim f/g = 0 alors g∉O(f) et f∈O(g)