Algorithmes, notion de complexités!

Logiciel & apps Programmation
1

Bonjour à tous, je suis étudiant en biologie médicale et je ne connais rien en programmation! J ai eu un cour de bioinfo qui introduisait les algo… J étudie pour mes exams de janvier et je ne comprends pas les notions de complexité en temps et en espace, je comprends leurs définitions, le problème que cela pose au niveau des ressources informatiques mais je ne comprends pas comment les calculer!

Pouvez vous m aider ou m orienter sur un site qui explique en gros (le but n est pas de faire de la programmation mais de comprendre) la méthode à suivre?

Merci bcp!!!

2

Ca s’appel la complexité algorithmique.

3

oui merci j’avais déjà regardé dans wikipedia, j’ai bien compris qu’en fonction des différents temps et espace de mémoire on attribue différentes annotations, mais je ne comprends pas comment on le fait pour calculer, comment dire dans cet algo c’est un temps constant, dans un autre c’est quadratique idem pour l’espace de mémoire.

4

Bah c’est une évaluation de sa complexité s’il est implémenté.

Genre:

Pour chaque élément f de F
Pour chaque élément g de G
Si f != g Alors: Ajoute f dans H
Fin Pour
Fin Pour

Je sais pas ce que fait l’algo, mais tu vas évaluer la complexité temps par rapport aux “instructions”:

Pour chaque élément f de F ---------> F a n éléments
Pour chaque élément g de G ---------> G a m éléments
Si f != g Alors: Ajoute f dans H ---------> à priori, si c’est une liste = temps constant
Fin Pour
Fin Pour

Donc la complexité temps sera n*m.

5

merci de tenter de m’expliquer mais je ne comprends tjs pas :frowning:

je vous montre le genre de prob que je dois résoudre :

Problème : trouver la plus grande suite de nucléotides identiques dans une séquence d’ADN

Input : entier n
Séquence d’ADN S de longueur n (tableau dont chaque position est un caractère dans {A,C,G,T).

Output : la longueur l de la plus longue suite de nucléotides identiques dans S (1<l<n)
la position p de début de cette suite (1<p<n-l+1)

ça sera quoi dans cet exemple la complexité?

6

Faut déjà que t’écrive l’algorithme, je ne le ferai pas pour toi : c’est que je suis pas spécialiste en ADN.

Ensuite on verra, mais c’est super simple.

7

à la base on a que ça à notre disposition, il faut absolument écrire l’algo pour trouver la comlpexité en temps et en espace? juste avant en 3 pages il décrit l’écriture d’algo mais avec un tableau et on recherche un nombre manquant ça je trouve facile, mais plusieurs données entrent en jeu…
Edité le 31/12/2007 à 16:49

8

Heu la base pour calculer la complexité, c’est d’avoir l’algorithme.

Tu ne trouveras jamais la complexité sans l’algorithme.

Y a peut-être des exceptions comme les tris, démontrés comme étant en O(log(n)) au mieux, mais ça s’arrête à là.

Et dernière chose, c’est toujours la complexité dans le pire des cas. Jamais dans le meilleur.

9

j’ai un petit article la dessus : www.geekz.fr…

peut-etre que cela t’aidera :neutre: