Salut
J'ai écrit un algo itératif qui donne la plus grande séquence de 1 dans un tableau à 1 dimension contenant des 0 et des 1.
Le voici :
Je dois trouver la complexité pire-cas et meilleur cas de cet algo.
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
19 fonction maxSeq1(T,i,j) p <- 0 // position de la plus grande sequence de 1 n <- 0 // longueur de la plus grande sequence de 1 b <- 0 // longueur de la sequence courante de 1 pour k de i à j faire si T[k] = 0 alors b <- 0 sinon b <- b + 1 si b > n alors p <- k - b + 1 n <- b finSi finSi finPour retourner (p,n) finFonction
J'ai trouvé : complexité pire-cas = complexité meilleur-cas = j - i + 1 (nombre de fois qu'on passe dans le pour etant donné que le reste est en o(1)).
Ma question est simple : ai je bon ?![]()
Merci à vous
Partager