Notations et compléxité

**vinzzzz** · 09/01/2007, 21h00

Hello
J'ai une question quand aux notations et a la signification de certaines de ces notations en algorithmique:
Ce sont les trois premières dans ce liens la:
http://www.etis.ensea.fr/~revel/html...es/node22.html
les trois premières dans la section "notations assymptotique": omega(n), O(n) et "Obarré(n)"

Je les ai souvent rencontrées, mais j'arrive pas a comprendre leurs signification exacte (en francais, parce que j'ai croisé moultes formules qui ne m'ont pas aidé...)
Je sais que ca a un rapport avec la complexité, le nombre d'opération ou le temps d'un algorithme, mais j'aimerai comprendre leur significations exactes...

Si quelqu'un peut éclairer ma lanterne

Merci d'avance

**PRomu@ld** · 09/01/2007, 23h11

L'oméga de n t'indique une complexité minimale minorante pour ton algorithme. En français ça t'indique que ton algo dans le meilleur des cas ne pourra faire que comme cette fonction.

Si tu trouve un algo qui est dans oméga d'une fonction exponentielle, ça veut dire que ton algo dans le meilleur des cas pourra se rapprocher de la fonction exponentielle mais ça veut aussi dire qu'il pourra être bien pire.

La notation grand 0 t'indique au contraire une borne suppérieure. Ca veut dire que dans le pire des cas ton algo se comportera comme cette fonction mais pas pire. (c'est sans doute la notation la plus utilisée).

La notation théta (ce que tu as appelé o barré) t'indique à la fois une borne suppérieure et une borne inférieure. La complexité est alors définie plus finement. Tu arrives donc à "cerner" le comportement de ton algorithme.

tous les tris sont en omega(n) puisque quelque soit le tri, il faut au moins n opérations pour réaliser le tri, c'est une borne inférieure.

La plupart des tris de base sont dans 0(n^2), celà signifie qu'il faudra en général au maximum n^2 opération pour réaliser le tri.

Le tri par tas est en Théta(n log n) puisque l'on sait qu'il faut exactement n log n opérations pour trier.

Le fait d'utiliser l'une ou l'autre des définitions dépend du contexte d'étude. Des fois on veut prouver que l'algo n'est "pas bon" alors on cherche un minorant qui est une fonction assez "méchante" (une exponentielle par exemple), on cherche donc à trouver l'oméga.

Des fois, on veut prouver que notre algorithmes n'est pas si mal que ça alors on cherche un bon majorant (une fonction polynomiale ou linéaire). On cherche donc le grand 0.

Et d'autres fois, lorsque celà est possible, on peut quelque fois (mais ça reste rare) chercher à savoir le nombre exacts d'opérations que l'on va éxécuter, c'est le théta.

**vinzzzz** · 09/01/2007, 23h35

Merci beaucoup pour tes explications...

Je comprendrais jamais pourquoi pour quelque chose qui s'explique facilement en francais, on vois si peu souvent cette explication accompagner la formule associée...

En tt cas merci encore.

**PRomu@ld** · 09/01/2007, 23h41

Pour moi la solution est simple : la notation mathématique est plus concise, plus formelle et surtout universelle !

De plus les formules ne sont pas bien compliquée ...