Discussion :

[CliffeCSTL]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[pseudocode]

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 )

[CliffeCSTL]

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.

[pseudocode]

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 ?

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".

[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.

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

[pseudocode]

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.

[CliffeCSTL]

Si j'ai un algo du type :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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) ...

[pseudocode]

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.

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é

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.

[CliffeCSTL]

p et m constantes.

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

[pseudocode]

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 )