La complexité algorithmique

[Rockleader]

Salutation, alors; vous allez surement me demander pourquoi poser des questions là dessus :hum: ?

Et bien tout simplement car aussi improbable que cela puisse être c'est une "matière" que j'apprécie réellement et qui me donne envie de creuser, j'en aurais presque une larmichette :doh:

Malheureusement pour moi; l'intérêt ne fait pas tout, et mes cours me laissent un gout amer d'incertitude et d'incompréhension. :cry:


Si je devais résumer ce que j'ai compris; ce sont les notations de théta; petit o; oméga et grand O.

Là dessus je pense que je maîtrise mon sujet.

Mais c'est bien beau de connaître des définitions de ce style (ainsi que sur les temps moyens); mais si on ne sait pas appliquer sur des cas concret.


Ce que je voudrais savoir c'est comment détermine on au final la complexité d'un algorithme donné. Je pense qu'il y a des règles; mais elles sont mal; voir non énoncé dans mon cours. La seule qui apparaît un tant soit peu clairement c'est qu'une affectation est de l'ordre théta de 1.

[Ben314]

Salut,
Mon domaine, c'est plus les math que l'info., mais je pense que pour comprendre le concept de complexité, ben l'idéal... c'est de prendre des exemples.
La plupart du temps, LE exemple pas mal du tout, c'est les algorithmes permettant de trier un tableau de données (réels ou entiers). Tu n'as pas eu de T.D. sur le sujet ?
Sinon, tu peut essayer de réfléchir à comment toit tu procèderais pour trier un tel tableau, puis à analyser la "complexité" de ton algorithme en comptant par exemple le nombre de comparaisons (ou d'affectations ou d'échanges) qu'il lui faut pour trier un tableau de taille n.
Ce nombre va évidement dépendre de n et la plupart des algo de tris "simples" qui viennent à l'esprit sont en O(n^2) (i.e. le nombre de comparaisons est proportionnel au carré de la taille du tableau), mais en fait, il existe plusieurs algo. plus rapides qui sont en O(n.ln(n)) et il y a une preuve assez jolie qu'on ne peut pas faire mieux que ce O(n ln(n)) (en terme de nombre de comparaisons partant d'un tableau totalement aléatoire)

Tout ça pour expliquer que, en général, la complexité ça s'exprime en fonction de la "taille" de ce que tu as à traiter (un nombre n de valeurs numériques ou de point ou la taille d'une matrice ou...)

[ampholyte]

Bonjour,

Voici le copier-coller d'un cours que j'ai trouvé très facile à comprendre avec des explications et des exemples concrets.

Source : http://www.france-ioi.org/, si tu es intéressé par les algo, je te recommande fortement ce site qui je trouve très sympa pour progresser en algorithme rapidement.

Je ne peux pas te donner le cours depuis le site (car il faut avoir atteint le niveau 3, pour le débloquer) donc je te donne une archive contenant les fichiers en .htm (ouvrable par navigateur).

Tu y trouveras des exemples, un cours et des petits exercices (la correction est affichée mais essaye de la cacher avant de la regarder).

Voici le lien : http://dl.free.fr/r4Eagy7N0

Si tu as des questions, n'hésite pas.

[Rockleader]

Je vous remercie, je me plonge là dedans aussi vite que possible !