Calcul Complexité Algorithme

[Cliffe]

BOnjour,

J'ai besoin d'aide pour calculé 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: Tout sélectionner

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


Merci.

[ampholyte]

Bonjour,

Pour calculer la complexité algorithmique il faut se placer dans le plus mauvais cas.

Code: Tout sélectionner

Pour i = 0 à n

=> La complexité de la boucle for est O(n+1)

Code: Tout sélectionner

Pour j = i + 1 à n

=> La complexité de la boucle for est O(n)

Code: Tout sélectionner

 Pour chaque label Li du nœud i

=> La complexité de cette boucle est O(p) car tu as p label pour chaque Li (dans le pire des cas)

Code: Tout sélectionner

 Pour t = 1 à p

=> Ici on a O(p)

Code: Tout sélectionner

 Pour chaque label Lj du noeud j

=> O(p) dans le pire des cas

Code: Tout sélectionner

  Appliquer un algorithme en o(m)

=> O(m)

Au final tout cela te donne une complexité de : O(mnp²(n+1)) erreur incluse :zen:

As-tu compris le calcul ?