Discussion :

[lee.mao]

Bonjour,

J'ai un algorithme qui traite un graphe avec n nœuds et m arcs ( |nœuds| = n et |arcs| = m). La complexité de cet algo est n²+n.m²

Quel est votre avis sur cette complexité ? est ce qu'elle est très mauvaise ?

Merci

[WhiteCrow]

Bonjour,

la complexité (temporelle je suppose) d'un algorithme permet d'en comparer le comportement asymptotique avec ou d'autres algos ou une complexité théorique optimale. Une simple complexité donnée sans plus de contexte ne sert pas à grand chose. Aucun algo n'est bon «dans l'absolu».

Pour se faire une idée plus précise il faut aussi contextualiser les données traitées. Par exemple un insertion sort (en O(n²)) sera meilleur qu'un merge sort (en O(n log n)) si les données à trier le sont presque. Pourtant, par réflexe on pourrait dire que O(n²) c'est pire/moins bien qu'un O(n log n) … De manière similaire si tu veux comparer un Kruskal (O(E log V)) avec un Prim (O(E+V log V)), en notant plus classiquement V le nombre de nœuds et E le nombre d'arrêtes, on ne peut qu'affirmer que Prim traitera sans doute plus efficacement un graphe dense.
Il y a aussi les cas extrêmes comme AKS qui détermine la primalité d'une nombre en temps polynomial n'est pas utilisé à cause des grandes constantes que l'on omet avec une complexité asymptotique.

Donner une complexité temporelle d'algo sans contexte ne permet pas de dire grand chose. Ici on peut tout au plus dire que plus ton graphe sera dense et pires seront ses temps de réponses, car on peut comparer les complexité d'un algo avec des données particulières. Si c'est un algorithme de connexité il est sans doute très mauvais, en revanche s'il résout le problème du voyageur de commerce alors il est exceptionnellement bon.

Bref, dis nous en plus.

[lee.mao]

Merci

L'algorithme en question exécute certains calculs et cherche les plus court chemins, il est composé de 3 parties:
1- Un simple calcul en parcourant les nœuds du graphe --> complexité n
2- La construction d'un arbre de plus court-chemin --> complexité n²
3- Parcourir l'arbre pour faire des tests sur les arcs --> complexité n.m² (m est le nombre des arcs)

Je ne sais pas si j'ai bien répondu à la question ?

[WhiteCrow]

Je suppose que le graphe est orienté ? les arcs ont-ils des poids ? les poids peuvent-ils être nuls ou négatifs ? les graphes traités sont-ils quelconques ou particuliers ?
Le plus court chemin … d'un nœud à un autre ? d'un nœud vers tous les autres (je suppose que c'est cela) ? de tous les nœuds vers tous les autres ? chemin hamiltonien ? chemin eulérien ?

Le plus simple serait sans doute d'exposer dans un premier temps le problème que tu cherches à résoudre, puis à nous montrer l'algorithme que tu as pondu.

[lee.mao]

Merci beaucoup WhiteCrow pour ces éclaircissements

[mach1974]

Il faut étudier la théorie de la complexité .
Un arbre où tu ne passes qu'une fois revient à du O n ln n pour l'algro de roy

l'application la plus évidente est le MPM ou le PERT