Notations et compléxité

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

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.

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.

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 ...

C'est sur, mais pour rendre la chose accessible plus facilement a tous, c'est quand même un plus d'expliquer clairement :)
Au pire, on met l'explication en anglais pour le coté universel ;)

Citation:

---

C'est sur, mais pour rendre la chose accessible plus facilement a tous, c'est quand même un plus d'expliquer clairement

---

La définition mathématique est claire, le tout est de la comprendre.

Citation:

---

Au pire, on met l'explication en anglais pour le coté universel

---

Les mathématiques sont plus universelles que l'anglais, ca n'est pas une bonne idée.

Citation:

---

La définition mathématique est claire, le tout est de la comprendre.

---

Justement, apporter une petite explication en plus aide a la comprendre plus vite...

Citation:

---

Les mathématiques sont plus universelles que l'anglais, ca n'est pas une bonne idée.

---

Ce n'était pas une proposition sérieuse :)

Citation:

---

Envoyé par PRomu@ld

La définition mathématique est claire, le tout est de la comprendre.

---

Yep, mais à la base de toute définition mathématique, il y a en général une idée intuitive.

Par exemple, je sais pas, la définition de la continuité, ou de la connexité par arcs, ce sont quand même à la base des choses très visuelles.

Et comprendre la définition formelle ne suffit pas à saisir le concept véritable qui se cachait derrière la chose.

Moi j'ai toujours aimé des illustrations, au delà des définitions formalisées.

Après, il arrive qu'on construise par hasard d'autres choses intéressantes n'ayant rien à voir, mais c'est une autre histoire.

Alors il n'y a donc que moi où un truc de ce genre est simple à comprendre ?

http://www.etis.ensea.fr/~revel/html/graphes/img124.gif

Si f(n) est dans O(n) alors ça veut dire qu'il existe deux constantes c et n0 dans l'ensemble des nombres réels positifs stricts tel que pour tout n suppérieur à n0 on a 0 <= f(n) <= c * g(n) ... , en clair à partir d'un certain rang, la fonction sera majorée par une autre à un facteur constant près.

La définition est ici tout de même relativement basique et son interprétation est plutôt directe ... . Je ne pense pas avoir un niveau exceptionnel en math pour comprendre ça.

Il faut avoir un minimum pour pouvoir comprendre certaines choses, en algorithmique il arrive qu'on fasse des choses qui ne sont pas très triviales mais ici ça l'est.

Non mais moi je la comprends bien, mais je veux dire aussi que les gens ne sont pas tous égaux devant des notations.

Des personnes peuvent ne pas être habitués à l'analyse basique dans le cas présent, et donc ça n'est pas forcément immédiat, parfois ça ne parle pas.

Je ne dis pas qu'une simple définition est insuffisante, mais pédagogiquement c'est souvent mieux d'avoir autre chose, c'est tout :).

PS : bon après, tu pourras me critiquer sur l'algorithmie sans avoir un minimum de bases en analyse ou autre :lol:. Moi je voulais parler plus généralement.

La notation mathématique il faut l'apprendre à l'école, et je crois que pour cette expression il faut avoir minimum le niveau Terminal S finie. Et pour les notations comme le A renversé, on l'apprend plus au lycée donc voila...