IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

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


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Novembre 2004
    Messages
    528
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Chef de projet en SSII

    Informations forums :
    Inscription : Novembre 2004
    Messages : 528
    Points : 99
    Points
    99
    Par défaut [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

  2. #2
    Membre régulier Avatar de O( N )
    Homme Profil pro
    Développeur Web
    Inscrit en
    Juillet 2006
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : Juillet 2006
    Messages : 126
    Points : 120
    Points
    120
    Par défaut
    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...
    Dans la vie il faut se cultiver ! Je suis développeur,
    je cultive des bogues.

    Citer c'est avouer qu'on a les mêmes idées que d'autres
    sans être capable de faire des phrases soit même ! - moi

  3. #3
    Membre régulier
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Novembre 2004
    Messages
    528
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Chef de projet en SSII

    Informations forums :
    Inscription : Novembre 2004
    Messages : 528
    Points : 99
    Points
    99
    Par défaut
    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

  4. #4
    Membre régulier Avatar de O( N )
    Homme Profil pro
    Développeur Web
    Inscrit en
    Juillet 2006
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : Juillet 2006
    Messages : 126
    Points : 120
    Points
    120
    Par défaut
    Tu passes de O(m*n) à O(1*N)
    puisque m représente la longueur
    de ton mot à trouver !
    Dans la vie il faut se cultiver ! Je suis développeur,
    je cultive des bogues.

    Citer c'est avouer qu'on a les mêmes idées que d'autres
    sans être capable de faire des phrases soit même ! - moi

  5. #5
    Membre averti

    Profil pro
    Étudiant
    Inscrit en
    Décembre 2004
    Messages
    499
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2004
    Messages : 499
    Points : 422
    Points
    422
    Par défaut
    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)

  6. #6
    Membre régulier
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Novembre 2004
    Messages
    528
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Chef de projet en SSII

    Informations forums :
    Inscription : Novembre 2004
    Messages : 528
    Points : 99
    Points
    99
    Par défaut
    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)

  7. #7
    Membre éprouvé
    Avatar de ol9245
    Homme Profil pro
    Chercheur
    Inscrit en
    Avril 2007
    Messages
    985
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 62
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Avril 2007
    Messages : 985
    Points : 1 158
    Points
    1 158
    Billets dans le blog
    1
    Par défaut
    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
    "La vraie grandeur se mesure par la liberté que vous donnez aux autres, et non par votre capacité à les contraindre de faire ce que vous voulez." Larry Wall, concepteur de Perl.

  8. #8
    Membre régulier
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Novembre 2004
    Messages
    528
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Chef de projet en SSII

    Informations forums :
    Inscription : Novembre 2004
    Messages : 528
    Points : 99
    Points
    99
    Par défaut
    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

  9. #9
    Membre éprouvé
    Avatar de ol9245
    Homme Profil pro
    Chercheur
    Inscrit en
    Avril 2007
    Messages
    985
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 62
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Avril 2007
    Messages : 985
    Points : 1 158
    Points
    1 158
    Billets dans le blog
    1
    Par défaut
    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).
    "La vraie grandeur se mesure par la liberté que vous donnez aux autres, et non par votre capacité à les contraindre de faire ce que vous voulez." Larry Wall, concepteur de Perl.

  10. #10
    Membre régulier
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Novembre 2004
    Messages
    528
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Chef de projet en SSII

    Informations forums :
    Inscription : Novembre 2004
    Messages : 528
    Points : 99
    Points
    99
    Par défaut
    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

  11. #11
    Membre éprouvé
    Avatar de ol9245
    Homme Profil pro
    Chercheur
    Inscrit en
    Avril 2007
    Messages
    985
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 62
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Avril 2007
    Messages : 985
    Points : 1 158
    Points
    1 158
    Billets dans le blog
    1
    Par défaut
    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
    "La vraie grandeur se mesure par la liberté que vous donnez aux autres, et non par votre capacité à les contraindre de faire ce que vous voulez." Larry Wall, concepteur de Perl.

  12. #12
    Membre régulier
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Novembre 2004
    Messages
    528
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Chef de projet en SSII

    Informations forums :
    Inscription : Novembre 2004
    Messages : 528
    Points : 99
    Points
    99
    Par défaut
    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

  13. #13
    Membre éprouvé
    Avatar de ol9245
    Homme Profil pro
    Chercheur
    Inscrit en
    Avril 2007
    Messages
    985
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 62
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Avril 2007
    Messages : 985
    Points : 1 158
    Points
    1 158
    Billets dans le blog
    1
    Par défaut
    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
    "La vraie grandeur se mesure par la liberté que vous donnez aux autres, et non par votre capacité à les contraindre de faire ce que vous voulez." Larry Wall, concepteur de Perl.

  14. #14
    Membre régulier
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Novembre 2004
    Messages
    528
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Chef de projet en SSII

    Informations forums :
    Inscription : Novembre 2004
    Messages : 528
    Points : 99
    Points
    99
    Par défaut
    Un tout grand merci pour ces explications...

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

    Encore merci

  15. #15
    Membre régulier
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Novembre 2004
    Messages
    528
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Chef de projet en SSII

    Informations forums :
    Inscription : Novembre 2004
    Messages : 528
    Points : 99
    Points
    99
    Par défaut
    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

  16. #16
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut [Off Topic] Pour la beauté du geste...
    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)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  17. #17
    Membre éprouvé
    Avatar de ol9245
    Homme Profil pro
    Chercheur
    Inscrit en
    Avril 2007
    Messages
    985
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 62
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Avril 2007
    Messages : 985
    Points : 1 158
    Points
    1 158
    Billets dans le blog
    1
    Par défaut
    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 )
    OL
    "La vraie grandeur se mesure par la liberté que vous donnez aux autres, et non par votre capacité à les contraindre de faire ce que vous voulez." Larry Wall, concepteur de Perl.

  18. #18
    Membre éprouvé
    Avatar de ol9245
    Homme Profil pro
    Chercheur
    Inscrit en
    Avril 2007
    Messages
    985
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 62
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Avril 2007
    Messages : 985
    Points : 1 158
    Points
    1 158
    Billets dans le blog
    1
    Par défaut
    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
    "La vraie grandeur se mesure par la liberté que vous donnez aux autres, et non par votre capacité à les contraindre de faire ce que vous voulez." Larry Wall, concepteur de Perl.

  19. #19
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    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

    [sarcasme] ca m'apprendra à ramener ma science [/sarcasme]
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  20. #20
    Membre régulier
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Novembre 2004
    Messages
    528
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Chef de projet en SSII

    Informations forums :
    Inscription : Novembre 2004
    Messages : 528
    Points : 99
    Points
    99
    Par défaut
    Citation Envoyé par ol9245
    et n'oublie pas, en vélo : plus tu pédales moins vite, moins ta vitesse est plus grande )
    OL
    Celle là je vasi le ressortir un jour... tres joli
    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à

Discussions similaires

  1. [XL-2013] Quel est la diférence entre ces deux tableaux ?
    Par Nono Sto dans le forum Macros et VBA Excel
    Réponses: 16
    Dernier message: 22/08/2014, 16h33
  2. Quel est l'ordre de cet algorithme récurrent ?
    Par meditx dans le forum Mathématiques
    Réponses: 1
    Dernier message: 28/11/2010, 20h27
  3. Réponses: 1
    Dernier message: 24/02/2009, 22h31
  4. Quel est la différence entre ces deux écritures ?
    Par TocTocKiéLà? dans le forum C++
    Réponses: 5
    Dernier message: 06/08/2007, 15h11
  5. Agata ou DataVision ? Quel est le meilleur de ces 2 outils pour le reporting ?
    Par titlola dans le forum Autres outils décisionnels
    Réponses: 1
    Dernier message: 16/05/2006, 16h39

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo