Complexité d'un algorithme récursif

Version imprimable

22/05/2010, 10h59
Erable

Complexité d'un algorithme récursif

Bonjour,

J'ai créé un algorithme (récursif) qui calcule tous les chemins possibles à partir d'un point d'un graphe orienté, et j'observe qu'à partir de quelques dizaines de points, le temps d'exécutions le temps d'exécution devient trop long. Cela est dû au fait que le nombre de chemins possibles croît très vite dès qu'on rajoute des points.

Mais peut-on dire que c'est lié à la complexité de l'algorithme? J'ai des difficultés avec ces notions, comment la calculer (approximativement?)? Elle dépend de la taille de la matrice d'adjacence et du nombre de tests qu'elle implique je présume.

Merci
22/05/2010, 12h40
pseudocode

Citation:

Envoyé par Erable

Mais peut-on dire que c'est lié à la complexité de l'algorithme? J'ai des difficultés avec ces notions, comment la calculer (approximativement?)? Elle dépend de la taille de la matrice d'adjacence et du nombre de tests qu'elle implique je présume.

Elle dépend surtout de l'algorithme. :D

Approximativement, la complexité est N*C(f) avec N le nombre total d'appel récursif de la fonction f() et C(f) la complexité de la fonction f.

Donc, en considérant que la fonction f() à toujours la meme complexité (= le meme traitement a chaque fois, on en déduit que la complexité dépend surtout du nombre d'appel récursif. Et là, il faut voir le détail de ton algo pour connaitre l'espace d'exploration (noeuds, arcs, ...) et en calculer la taille.
28/05/2010, 20h06
violet

Citation:

Envoyé par Erable

Bonjour,

J'ai créé un algorithme (récursif) qui calcule tous les chemins possibles à partir d'un point d'un graphe orienté, et j'observe qu'à partir de quelques dizaines de points, le temps d'exécutions le temps d'exécution devient trop long. Cela est dû au fait que le nombre de chemins possibles croît très vite dès qu'on rajoute des points.

Mais peut-on dire que c'est lié à la complexité de l'algorithme? J'ai des difficultés avec ces notions, comment la calculer (approximativement?)? Elle dépend de la taille de la matrice d'adjacence et du nombre de tests qu'elle implique je présume.

Merci

Dans le cas d'une explosion combinatoire le problème serait considéré NP-complet.
29/05/2010, 00h38
Djakisback

Sinon par curiosité, que veux-tu dire par "qui calcule tous les chemins possibles à partir d'un point d'un graphe orienté" ? car tu parles de sommets mais pas d'arêtes. (en fait, c'est ton "le nombre de chemins possibles croît très vite dès qu'on rajoute des points" qui me fait douter :D)

Est-ce que tu veux dire que tu fournis en entrée un graphe orienté ou bien seulement des sommets et que de là tu crées tous les chemins possibles, pour créer un graphe orienté ?
D'ailleurs j'en profite pour demander un truc, est-ce qu'il y a un nom pour un graphe orienté dont toutes les paires de sommets sont reliées pas des arcs (i,j) et (j,i) ? Est-ce que c'est ça un graphe complet ?