Bonjour à tous,
J'expose mon probleme avant de poser ma question:
J'ai des données en vecteurs comme ceci (elles sont ordonnée les donnée, par exemple des noms de famille)
[a b c d e .... z]...bon, y a pas que 26 data, masi bcp plus (exemple: 100.000)
et j'ai des données à analyser (des noms de familles), par exemple [1 2 3 ... 9] (pas ordnonnées)
Je compare les donées 123 avec abc pour trouver quelles 123 se trouve en abc comme ceci:
je prends le premier: "1" et je compare au reste"a", "b", "c", "d",..."z"
Ensuite je prends "2" et je compare "a,"b" ,"c","d",..."z".
ainsi de suite.
quelle est la comlexité? cad si j'ajoute "10" à "1","2","3",... , j'aurai 26 comparaison en plus à faire (si on prend le cas de l'alphabet. Mais je ne sais pas comment puis-je dire la complexité? elle est linéaire?
Ensuite, avec ces meme données abc, je fais une matrice carrée(je rappel que c'est ordonné)
( 4x4... bon il m'en manquera mais c'est pour l'exemple)
[ a b c d]
[ e f g h ]
[ ]
[ ]
et je fais un algo different:
je prends "1" et je le compare à au dernier element de chaque ligne
Exemple:
si "1" plus grand que "d" alors continuer
si "1" plus petit que "h", alors "1" est compris entre "e" et "h" (car il est plus grand que "d".
et ensuite je parcours la ligne un à un pour voir où se trouve "1".
La complexité de sa je rame??? je ne sais pas de quelle complexité il s'agit!
Enfin, j'ai un denier algo que j'utilise toujours avec la meme matrice. Je compare avec la fin de chaque ligne mais je ne comment pas par la premeir ligne, je commence avec la ligne du milieu.
Si "1" plus petit que le dernier element de la ligne du milieu, à il se trouve dans la moitié du dessus de la matrice, de ce fait, j'elimine d'un coup la moitié des valeur. En suite le compare avec la valeur de la ligne 1/4 (donc je subdivise les ligne en deux à chque recherche, lorsque je trouve la ligne, je fais la meme chose avec les colonne.
Exemple parlant:
[a b c d e]
[f g h i j]
[k l m n o]
[p q r s t]
[u v w x y]
donc c'est 5 x 5 et imaginons que je recherche la valeur de "1" qui est = à "q"
je compare "1" à "o", il est plus grand, j'elimine alors les lignes 1 à 3, il reste
[p q r s t]
[u v w x y]
je prends le milieu (2 ligne / 2 = 1), je prends le dernier element et je compare:
"1" par rapport à "t", il est plus petit
Donc "1"' se trouve en cette ligne[p q r s t]
On recommence avec les colonne:
"1" par rapport à "r", plus petit, j'elimine le reste, il reste:
[p q ]
le milieur est "p", c plus grand, on arrive alors à "1" = "q"
J'espere que vous avez pas mal à la tete et que j'ai été assez clair!
Pourriez-vous avec precision me donner la complexité des ces 3algorithmes
Partager