Bonjour j'ai un problème de complexité :


Code C : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
 
int count (int *T, int n)
{
   int j;
   if (n == 0)
      return 0;
   j = 1;
   while ((n-1-j >= 0) && (T[n-1-j] != T[n-1]))
      j = 2*j;
   if (n-1-j >= 0)
      return count(T, n-1);
return (count(T, n-1)+1);
}



Donc dans le pire des cas la boucle while sera effectué (n-1)*(n-2) fois. n-1 fois pour l'itération et n-1-j fois pour l'itération de while ? D'ou en minorant j par 1.

D'ou T(n) = n*T(n-1) D'ou une complexité polynomiale.