Calcul Complexité Algorithme

BOnjour,

J'ai besoin d'aide pour calculer la complexité de mon algorithme :

Soit n, p et m des entiers.
Soit H un graphe composé de n+1 sommets notés (0, 1, 2, ..., n).

Voila le code minimal :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

L0 = [0, 0, ..., 0] // De taille 'p' Poser L0 sur le nœud 0; Pour i = 0 à n faire Pour j = i + 1 à n faire Pour chaque label Li du nœud i faire Pour t = 1 à p faire Si Li[t] + 1 <= m Lnew = Li; Lnew[t] += 1; Pour chaque label Lj du noeud j faire // Appliquer un algorithme en o(m) fait Poser Lnew sur le noeud j; fsi fait fait fait fait

---

Merci.

Pour I = constante à N faire
  X
fait

Ce code fait, au maximum, N fois l'opération "X".
Il a donc une complexité en o( N*Complexité(X) )

Si on applique ce principe a ton code, on obtient une complexité en o( n*n*size(label)*p*size(label)*m )

D'accord mais le nombre de label sur un noeud dépend de m et n. On doit pouvoir le calculer. De plus il y a un test "Si". Du coup les deux dernières boucles ne doit pas être prit en compte à chaque fois.

Citation:

---

Envoyé par CliffeCSTL

D'accord mais le nombre de label sur un noeud dépend de m et n. On doit pouvoir le calculer.

---

On ne cherche pas a le calculer, mais a le majorer. Combien peut-il y avoir de labels, au maximum du maximum ? N ?

Citation:

---

De plus il y a un test "Si". Du coup les deux dernières boucles ne doit pas être prit en compte à chaque fois.

---

idem. On cherche un majorant. Le cas le plus défavorable c'est lorsqu'on passe toujours dans le "Si".

Je suis pas d'accord. Le cas ou on passe tjr dans le "Si" n'existe pas. Je cherche à donner le résultat exacte.

J'ai déjà donné l'algo dans le pire des cas.

Citation:

---

Envoyé par CliffeCSTL

Je suis pas d'accord. Le cas ou on passe tjr dans le "Si" n'existe pas. Je cherche à donner le résultat exacte.

---

Il n'y a pas de "résultat exact" en complexité. Juste des ordres de grandeur, servant a classer un algo par rapport à un autre.

Le quickSort est en o(N^100). Il est au aussi en o(N^2). Et le plus souvent, sous certaines contraintes usuelles, en o(N.Log(N)). Le MergeSort est lui toujours en o(N.Log(N)). Pourtant, dans les faits, il est généralement moins rapide que le QuickSort.

Tout ce qu'on peut dire, c'est que ces deux algos ont une compléxité moyenne équivalente. Et c'est à cela que sert le calcul de compléxité.

Si tu veux avoir un "résultat exact", il faut une implémentation, des sets de données et faire un benchmark. ;)

:roll:

Si j'ai un algo du type :

Code:

---

1 2 3 4 5

Pour i = 1 à N faire Si i = 1 alors // Algo en o(m) fsi fait

---

La complexité pour toi est en o(N*m) ? pour moi c'est du o(m) ...

Citation:

---

Envoyé par CliffeCSTL

La complexité pour toi est en o(N*m) ? pour moi c'est du o(m) ...

---

La complexité s'exprime en fonction de la taille des données d'entrée.

:arrow: Le tri d'un tableau de taille N se fait en o(N.log N) comparaisons avec un MergeSort.


Si l'algorithme requiert des paramètres additionnels pour s'exécuter, ceux-ci peuvent être utilisés comme paramètres dans la formulation de la complexité

:arrow: La recherche du k-ième plus grand élément d'un tableau de taille N se fait en o(k.N) comparaisons avec un SelectionSort.


Bien sur, c'est a toi de décider quels sont les paramètres d'entrée et quelles sont les "constantes" dans ton algo. Le pseudo-code de ton premier post ne m'a pas permis de différencier les 2. :D

p et m constantes.

J'ai mis ça : o(n^2p^{2m+1}m) mais j'aime pas trop.

Citation:

---

Envoyé par CliffeCSTL

p et m constantes.

J'ai mis ça : o(n^2p^{2m+1}m) mais j'aime pas trop.

---

moi j'avais o( n*n*size(label)*p*size(label)*m ).

En considérant qu'au pire cas, on a autant de labels que de noeuds (size(label)< =n), ca donne: o( n^4 . p . m )