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 n2+n.m2
Quel est votre avis sur cette complexité ? est ce qu'elle est très mauvaise ?
Merci
Version imprimable
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 n2+n.m2
Quel est votre avis sur cette complexité ? est ce qu'elle est très mauvaise ?
Merci
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.
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 ?
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.
Merci beaucoup WhiteCrow pour ces éclaircissements
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
Bonjour,
La théorie de la complexité est très intéressante mais il faut l'associer avec le pragmatisme. Si elle donne bien les évolutions de comportements avec des ordres de grandeur élevés, elle est insensible au coûts fixes ou d'ordre inférieur à l'ordre de complexité de tel ou tel algorithme.
Ainsi le meilleur algorithme au sens de la complexité peut se révéler très mauvais pour les faibles volumes ou des évolutions incrémentales limitées parce qu'il nécessite un travail de préparation coûteux ou ne sait pas traiter que l'ensemble des données.
Par exemple, le quick sort n'est pas la meilleure solution pour trier un ensemble presque dans l'ordre ou des ajouts et mises à jours limités.
Salutations.
C'est pourquoi le buble short est préférable au Quick short
Il est vrai que les arguments avancés sont pertinents , mais le pert relève bien dans la théorie des graphes de n log n en application directe en dehors des problèmes de volumes et des coûts fixes qui seront quand même embarqués dans l'exécution de la première itération, sachant que le coût variable ne diminue pas avec le nombre d'iteration
Bonjour mach,
L'argument n.l.og(n) suppose que l'on parle du même n quand on compare deux algorithmes, ce qui peut s'avérer peu pertinent.Citation:
Envoyé par mach1974
Prenons un exemple. J'ai une base d'enregistrement triée d'un million d'entrées. J'y ajoute des paquets non triés de quelques milliers d'enregistrements (n') par jour.
Si je raisonne n.log(n) et choisis quick sort, je vais l'appliquer à un million + des cacahouètes soit en O((n+n').log(n+n')). Mais je peux aussi trier les paquets (éventuellement en QS soit n'.log(n') ) puis faire une fusion qui sera au pire en O(n). Ce n'est pas un cas d'école mais une situation réelle qui est très fréquente (même si c'est souvent transparent au sein des bases de données par exemple).
C'est pourquoi j'avais cité, d'une part, les coûts fixes et, d'autre part, l'aptitude aux traitements partiels et incrémentaux.
Cela ne retire absolument rien à l'intérêt de l'étude de la complexité. Cela veut juste inciter à prendre en compte l'usage des algorithmes pour éviter de faire d'emblée une comparaison brutale sur le seul critère O(...).
Salut