Discussion :

[Terminator]

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

[O( N )]

Bonjour

Pour ton premier algorithme il me semble que tu recherches un mot dans un dictionnaire ?
Donc la complexité de la recherche est de n*m avec m=longueur du mot recherché et n le nombre de mot présent dans le dictionnaire. KMP est un algorithme qui fait ceci trés bien, il me semble... en O(n+m) ? j'ai oublié (oups)

Donc la complexité est O(k*N) = > linéaire.

Ensuite tu créé ta matrice => O(N)
( répartie en longueur*largeur (N = 16 => 4*4))

Ensuite encore...
Tu recherches dans ta matrice tes éléments=> a peu prés
O(n*log(longeur))+O(log(largeur)) ou n est la longueur du mot que tu recherches.
le log car tu fait une recherche dichotomique
sur la longueur puis tu en fais une sur la largeur, si j'ai bien suivi ...

voilà ... mais je me suis peut-être trompé car je ne suis pas sûr de l'algo...

[Terminator]

Merci de tout coeur pour ta reponse!!

Malgré qu'effectivmeent ce soit une recherche de type dictionnaire, je ne veux pas prendre en compte la taille du mot!
En gros, je donne un exemple simple:

Je cherche "Mes" dans la ligne "Ma", "Mes","Mon"
Si c'est linaire, ca donne:
Mes == Ma
Si oui, stop, sinon
Mes = Mes
Si oui, stop, sinon
Mes=Mon

Je ne veux pas que la complexité prenne ten compte la longueur des mots (meme si c'est effectivement un recherche de dico.)

Bref, considerons que le mot ont TOUS les mots en une taille de 1 caractere (meme si c faux).

Donc quels changeemnt ca apporterai à ta reponse?

D'avance merci

[O( N )]

Tu passes de O(m*n) à O(1*N)
puisque m représente la longueur
de ton mot à trouver !

[acx01b]

salut

taille 1er paquet : n
taille 2eme paquet : m
si ton 2ieme paquet de données n'est pas trie :
O(log_2(n)*m)
--> m recherches dichotomiques sur une liste de taille n

si ton 2ieme paquet n'est pas trie mais que tu le tries avant:
O(m*log_2(m) + X)

--> où X est la complexite d'un match entre deux listes triees
probablement que la 1ere solution est mieux en tout cas car c'est presque sur que X > log_2(m)

[Terminator]

Merci acx01b pour ces precisions,

mais juste une petite question: les complexité que tu donne, c'est pour quel methode? car j'ai cité 3 méthodes

Je pense que c'est pour la troisieme, mais je veux etre certain !

D'avance merci

PS: tu confirme les reponses deO( N ) pour les 2 premiereS? (car il demande lui meme confirmation)