[Complexité algorithmique] quel est la complexité de ces algorithme?

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

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 ... :P

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

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

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

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)

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)

premier algo = la complexité est en N x M ou N est la taille du doco et M le nombre de requêtes
Deuxieme algo = tu sautes des mots pour aller plus vite quitte à revenir en arrière si tu as dépassé. Dans le meilleurs des cas tu vas 4 fois plus vite. = la complexité est la même. Pour mémoire, la complexité ne sert pas à comparer deux algos entre eux mais a déterminern comment le temps de calcul augmente avec la taille du problème. dans ton cas c'est clair = si la taille du dico double, l'algo 1 tout comme l'algo 2 doublent en temps de calcul.
Troisième algo = tu fais une recherche dichotomoque. chaque mot est trouvé en log(N) donc ton algo est e M * log(N)

Quatrième algo (que tu n'as pas cité dans ton bestiaire)
- trier les M mots à chercher (complexité M*log(M))
Le problème ser amène à une fusion. Tu peux la faire par dichotomie :
- chercher le mot du milieu par dichotomie (cout en log(N))
- ça coupe le dictionaire en deux morceaux a peu près de même taille. et la liste aussi est coupée en deux morceaux, exactement de meme taille. donc on est revenu à deux problèmes, chacun de taille moitié du premier en M ET en N. là je te laisse calculer la complexité lol c'est pas évident. si M=N, l'algo est en M+M*log(M) (le cout du tri). si M est petit devant N, il est en M*(log(N)+log(M)). Et dans le cas générl ?
OL

Merci pour les reponses,

Mais je suis pas d'acccord avec la reponse au deuximee algo.

"Au mieux, il va 4 fois pus vite"
FAUX.

Car si je prends l'exemple suivant: un premier tableau de 25 mots et un autre de 100. Si on fait en vecteur simple (deux vecteurs) ca fait: 25x100 = 2500 itérations AU PLUS.

Si on construit une matrice, ca donne une de 10 x 10 (si on construit la matrice sur le 100), donc au pire on fait 10 ligne et 10 colonne, donc 20 itération dans la matrice par donnée à analyser. Ca donne: 25 x 20 = 2500 (on est donc 5 x plus vite).

Mais si au lieu d'avoir 100 mots on a 10.000, alors la premier donne 25x10.000 = 250.000 itarations
Pour le second allgo, on a une matrice 100 x 100, au pire on fait 100 lignne et 100 colonne, donc 200 --> 200 x 25 = 5000, on va 50 fois plus vite. Donc plus on a de donnée dans le dico et plus le second algo ira plus vite que le premier. Non?

D'un autre coté je suis pas tres algo moi, c pour ca que je vous demande des eclaircissements

D'avance merci à tous

Citation:

---

Envoyé par Terminator

Merci pour les reponses,

Mais je suis pas d'acccord avec la reponse au deuximee algo.

"Au mieux, il va 4 fois pus vite"
FAUX.

Car si je prends l'exemple suivant: un premier tableau de 25 mots et un autre de 100. Si on fait en vecteur simple (deux vecteurs) ca fait: 25x100 = 2500 itérations AU PLUS.

Si on construit une matrice, ca donne une de 10 x 10 (si on construit la matrice sur le 100), donc au pire on fait 10 ligne et 10 colonne, donc 20 itération dans la matrice par donnée à analyser. Ca donne: 25 x 20 = 2500 (on est donc 5 x plus vite).

Mais si au lieu d'avoir 100 mots on a 10.000, alors la premier donne 25x10.000 = 250.000 itarations
Pour le second allgo, on a une matrice 100 x 100, au pire on fait 100 lignne et 100 colonne, donc 200 --> 200 x 25 = 5000, on va 50 fois plus vite. Donc plus on a de donnée dans le dico et plus le second algo ira plus vite que le premier. Non?

D'un autre coté je suis pas tres algo moi, c pour ca que je vous demande des eclaircissements

D'avance merci à tous

---

Oui, tu as raison, j'avais pas percuté sur la matrice carrée. J'étais sctotché sur ton exemple ou ta matrice fait 4 de large. Si ta "matrice" est carrée, il te faut racine(N) pour trouvet la ligne et ravine(N) pour la parcourir, donc finalement, tu es en M*racine(N).

Merci pour les preciseions
Je me permettrai de poser une autre question:

Dasn le troisieme algo, quel est le gain de rapidité par rapport au second?

Pour moi (exemple de matrice de 100 x 100):
dans le second:
au pire: (100 + 100) * nombre requete
Pour le troisieme:
(racine(100) + racine (100)) * nombre de requete

Donc le gaine est de racine du nombre de mots dans le dico, non?

D'avance merci

Citation:

---

Envoyé par Terminator

Merci pour les preciseions
Je me permettrai de poser une autre question:

Dasn le troisieme algo, quel est le gain de rapidité par rapport au second?

Pour moi (exemple de matrice de 100 x 100):
dans le second:
au pire: (100 + 100) * nombre requete
Pour le troisieme:
(racine(100) + racine (100)) * nombre de requete

Donc le gaine est de racine du nombre de mots dans le dico, non?

D'avance merci

---

le 3eme algo n'est pas en racine de N mais en Log(N) (pour une seule recherche). il y a pas photo entre un algo en Log(N) et un autre en racine(N).
D'ailleurs, pour ce 3eme algo, tu n'as absolument pas besoin e faire ta recherche dichotomique sur la matrice carrée. Autant la faire sur le tableau direct et bien droit. dans un cas, tu est en Log(N) pour le tableau complet, et en log(racine(N)) pour la version matrice. Or, log(racine(N)) = log(N)/2 mais tu n'a fait que la moitié du travail. Si tu refais une recherche dichotomique pour parcourir ta ligne, tu es enconre en log(N)/2, donc au finish, tu t'es compliqué la vie pour rien = ta recherche est finalement en log(N)/2 + log(N)/2 = log(N).
Des algos de recherche dichotomique, tu devrais en trouver des tout faits un peu partout.
OL

Merci pour ces précisions.

Mais il y a un petit quelque chose qui m'échappe pour le troisieme, (log)

Je ne comprends pas comment on arrive à en déduire que c'ets en log car moi je pars de la philosophie suivante:
Si matrice 100 x 100
je prends les lignes (100) et à chaque fois je découpe en 2, il me reste 50
De ces 50 lignes restantes, je redécoupe en 2, il reste 25
25 -> 13
13 -> 7
7 -> 4
4 -> 2
2-> 1

Donc j'ai fait que pire: 7 recherches
Et je dois refaire la meme chose pour les colonnes, donc j'ai en tout 14 recherches (itérations)!

le second aurait été de 200 itérations.

Je ne comprends pas comment vous arrivez à en déduire le log à partir de ca?

En tout cas, merci pour toutes ces reponses et cette aide :)

Citation:

---

Envoyé par Terminator

Je ne comprends pas comment vous arrivez à en déduire le log à partir de ca?

En tout cas, merci pour toutes ces reponses et cette aide :)

---

si tu double la taille du tableau, tu ajoute une seule comparaison. soit C le nombre de comparaisons, tu as donc la propriété suivante :
C(2*N) = C(N) + 1
donc
C(2N) - C(N) = 1

La fonction mathématique qui a cette propriété est la fonction log car on sait que log(2N) = log(2) + log(N)
ce qu'on peut écrire :
log(2N) - log(N) = log(2)

donc "quelquepart" on peut écrire :
C(N) = log(N)/log(2)

c'est pas rigoureux (ça marche pas pour N=1) mais c'est l'esprit.
J'explique ça à ma manière (je suis pas matheux)
Mais c'est très bien documenté dans n'importe quel bouquin d'algo.

Lis par exemple le Sedgewick. C'est très facile à lire (je l'ai lu dans le train) et les algos sont de toute beauté.
OL

Un tout grand merci pour ces explications...

A ta manière...mais tres bien expliqué!!!!
Au moins,j'ai compris :)

Encore merci

Cale dit, une toute dernière question:

Le troisième est quand meme plus rapide que le premier (je parle en rapidité pour une meme taille de probleme et dans le pire des cas pour chacun).

Mais de combien de fois plus rapide?
lors de mon avant denier post, j'avais mis le calcul, mais est-ce exact?

D'avance merci

Citation:

---

Envoyé par ol9245

C(2*N) = C(N) + 1

---

Changement de variable: N=2^t

C(2* 2^t ) = C( 2^t ) +1

c-a-d,

C(2^(t+1)) = C(2^t) +1

Par récursion, on obtient:

C(2^t) = C(2^(t-1)) +1 = C(2^(t-2)) +1 +1 = ... = C(2^0) + t = Constante + t

donc l'algo est en O(t).

Et, par changement de variable:

O(t) = O(log n)

il faut que tu lise un peu sur la complexité algorithmique. Ce ne sont pas des lectures très difficiles au moins pour commencer, et c'est très intéressant.

tu verras que un probleme quasi linéaire (N*Log(N)) est "en général" plus rapide qu'un problème polynomial (N^1.5, ou N^2). mais c'est à une constante multiplicative près.

En d'autres termes, ce qui est certain, c'est que il existe toujours une taille N de problème au-dela de laquelle l'algo quasi linéiare est avantageux. Mais cette taille de problème peut être très grande, voire, plus grande que la taille habituelle du problème posé.

Et pour répondre précisément à ta question, tu ne peux pas dire que l'algo 3 est 10 fois, 2 fois, ou x fois plus rapide que l'aglo 2. Ca n'a pas de sens, précisément parcequ'ils n'appartienntn pas à la même classe de complexité. Plus N est grand, plus l'algo 3 est plus rapide. (et n'oublie pas, en vélo : plus tu pédales moins vite, moins ta vitesse est plus grande :mouarf: )
OL

Citation:

---

Envoyé par pseudocode

Changement de variable: N=2^t

C(2* 2^t ) = C( 2^t ) +1

c-a-d,

C(2^(t+1)) = C(2^t) +1

Par récursion, on obtient:

C(2^t) = C(2^(t-1)) +1 = C(2^(t-2)) +1 +1 = ... = C(2^0) + t = Constante + t

donc l'algo est en O(t).

Et, par changement de variable:

O(t) = O(log n)

---

Ah oui, là c'est vraiment très joli. Beau geste !!! très émouvant. merci. (ca me met la larme à l'oeuil. en te lisant j'ai l'impression de m'encrouter). OL

Citation:

---

Envoyé par ol9245

Ah oui, là c'est vraiment très joli. Beau geste !!! très émouvant. merci. (ca me met la larme à l'oeuil. en te lisant j'ai l'impression de m'encrouter). OL

---

lol :lol:

[sarcasme] ca m'apprendra à ramener ma science [/sarcasme]

Citation:

---

Envoyé par ol9245

et n'oublie pas, en vélo : plus tu pédales moins vite, moins ta vitesse est plus grande :mouarf: )
OL

---

Celle là je vasi le ressortir un jour... tres joli :)

Citation:

---

Changement de variable: N=2^t

C(2* 2^t ) = C( 2^t ) +1

c-a-d,

C(2^(t+1)) = C(2^t) +1

Par récursion, on obtient:

C(2^t) = C(2^(t-1)) +1 = C(2^(t-2)) +1 +1 = ... = C(2^0) + t = Constante + t

donc l'algo est en O(t).

Et, par changement de variable:

O(t) = O(log n)

---

Bon, ben on a affaire un à mathématicien là :)