ALGO 1 : complexité

Aller en bas

ALGO 1 : complexité

Message  Azed le Mar 22 Sep 2009 - 18:55

Salut ! Je supplie les L3 qui ont ALGO 2/toute autre personne qui en aurait les compétences de m'aider dans cette matière euh... bizarre ?

1/ Dans le tout premier cours, la 7e diapo (le même que l'an dernier pour les L3, il est dispo sur le site que vous connaissez bien...) il y a une équation que je ne comprends pas. Je ne sais pas comment le prof fait pour arriver à ce résultat :

On a une fonction récursive :
Code:

    si (n > 1) alors
 
        Recursive(n/2), ( coût T (n/2) )
                             
        Traitement(n),  (coût C(n) )
                             
        Recursive(n/2), (coût T (n/2))

Je comprends les couts de chaque étape et je comprends donc que T(n)=2 ∗ T (n/2) + C(n).
Dans ce cas, pourquoi on a : si C(n) = 1 alors T (n) = K × n et si C(n) = n alors T (n) = K × n × log n ???

2/ Dans le TD 2 (2e méthode) où l'on cherche à calculer l'élément majoritaire on a une complexité qui vaut T(n)=1+2T(n/2)+2n= O(nlog2 n) "car T(n)= k1+k2n+2T(n/2))... euh pourquoi sa ???

Voici le code de l'algorithme en question :

Code:


Si E est le singleton {e} alors
          renvoyer E,

Scinder E en E1 et E2,

e1 := majoritaire (E1),
si e1 existe alors
          si(2*nombre d'occurrences (e1,E)> |E| (=cardinal de E, le nombre d'éléments de E)  alors
                              renvoyer e1,

e2:=majoritaire (E2),
si e2 existe alors
          si (2*nombre d'occurrences(e2,E2)>|E| alors
                                renvoyer e2,

renvoyer NO ELEMENT,

Merci d'avance!!!
avatar
Azed

Masculin Nombre de messages : 210
Age : 28
Localisation : Lyon
Humeur : La colocation c'est nul !
Date d'inscription : 20/09/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  funkyMat le Mar 22 Sep 2009 - 23:21

Pour te répondre :
Tout d'abord, tu te prends trop la tête sur les complexités ! C'est important, certes, mais ce qui est primordial, c'est de voir ce que va faire le programme "en gros" et non très précisèment.
L'expression "si C(n) = 1" veut dire "si n est petit" alors que l'expression "si C(n)=n" veut dire "si n est grand".
La page 22 te sera d'une aide précieuse.
Si je ne me trompe pas :
T(n)=2*T(n/2)+n
donc T(n/2)=2*T(n/4)+n/2
T(n)=4*T(n/4)+2n
T(n)=Somme(i=0;log(n-1))(2^i *n)+2^log(n)
T(n)=n*log(n)+n

donc T(n) = K*n*log(n)

Dans tous les cas, le plus important à retenir (et à savoir par coeur dans ce cours) est qu'une fonction récursive se résout, par la méthode itérative, en O(n*log n) et que "log(n)" est la hauteur de l'arbre (cf. page 23).

Pour répondre à ta question 2, tout est expliqué pages 21, 22 et 23 du 1er poly (le programme expliqué est très semblable au tien).

P.S. : J'explique très mal mais on en reparle à l'apéro si tu n'as pas tout compris ! Wink

_________________
"Sans la liberté de blâmer, il n'est point d'éloge flatteur", Beaumarchais
avatar
funkyMat
Admin

Masculin Nombre de messages : 571
Age : 31
Localisation : Marseille 9e
Date d'inscription : 05/06/2008

Voir le profil de l'utilisateur http://matthieu-gorlier.homeip.net

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  Azed le Mer 23 Sep 2009 - 18:40

Non tu n'explique pas très mal... c'est juste moi qui ne comprend rien à rien !

J'ai bien tout compris sauf le passage de T(n)=4*T(n/4)+2n à T(n)=Somme(i=0;log(n-1))(2^i *n)+2^log(n)
puis de T(n)=Somme(i=0;log(n-1))(2^i *n)+2^log(n) à T(n)=n*log(n)+n.

Mon problème vient des maths en fat... comme d'hab'.

Un gros merci pour me venir en aide cependant.
avatar
Azed

Masculin Nombre de messages : 210
Age : 28
Localisation : Lyon
Humeur : La colocation c'est nul !
Date d'inscription : 20/09/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  funkyMat le Mer 23 Sep 2009 - 20:30

Je t'explique demain, ça te va ?
Ce sera plus simple comme ça ! Et peut-être comprendras-tu en cours demain matin ?
A demain midi... Wink

_________________
"Sans la liberté de blâmer, il n'est point d'éloge flatteur", Beaumarchais
avatar
funkyMat
Admin

Masculin Nombre de messages : 571
Age : 31
Localisation : Marseille 9e
Date d'inscription : 05/06/2008

Voir le profil de l'utilisateur http://matthieu-gorlier.homeip.net

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  Azed le Mer 23 Sep 2009 - 22:07

Oki @ demain.
avatar
Azed

Masculin Nombre de messages : 210
Age : 28
Localisation : Lyon
Humeur : La colocation c'est nul !
Date d'inscription : 20/09/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  Azed le Ven 11 Déc 2009 - 13:30

C'est encore moi et mes problèmes de complexité (algorithmique, je précise au cas où...) :

Eh bien, dans votre exam d'algo de l'an dernier vous aviez une fonction joyeusement intitulée "bidon" et on doit en déduire sa complexité :
Code:

void bidon (int V[], int n)
{
    if (n<= 1) return;
    for(i=1;i<n;i++)
          if(V[i] < V[i-1]) {
                tmp=V[i-1];
                V[i-1]=V[i];
                V[i]=tmp;
          }
    bidon (V, n-1);
}

Bon je pense qu'on a T(n)=n+T(n-1).
Donc du coup on aurait un truc par méthode itérative qui serait T(n)=n+(n-1)+T(n-2)=n+(n-1)+(n-2)+T(n-3)=...=O(n²) ???????????????????????????

Merci d'avance pour votre précieuse aide.
avatar
Azed

Masculin Nombre de messages : 210
Age : 28
Localisation : Lyon
Humeur : La colocation c'est nul !
Date d'inscription : 20/09/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  funkyMat le Dim 13 Déc 2009 - 1:07

Pour moi, c'est en O ( n * ( (n+1) / 2 ) ).

Si, tu avais eu en appel de fonction récursive "bidon (V, n/2);", la complexité aurait été en O(n*log(n)).
Bon courage pour tes(vos) révisions...

_________________
"Sans la liberté de blâmer, il n'est point d'éloge flatteur", Beaumarchais
avatar
funkyMat
Admin

Masculin Nombre de messages : 571
Age : 31
Localisation : Marseille 9e
Date d'inscription : 05/06/2008

Voir le profil de l'utilisateur http://matthieu-gorlier.homeip.net

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  Azed le Dim 13 Déc 2009 - 16:45

D'après le cours : n(n+1)/2 = O(n² ). On a peu près la même complexité... Merci !

Mais je crois que je me suis trompé dans l'évaluation de T(n)... Je pense qu'en fait, T(n)=1+n+T(n-1) mais cela n'a aucune influence sur la complexité de cette fonction (pas vraiment un algorithme ce truc).

Bon courage à toi, flo, momo et tous les autres L3 ! Ainsi qu'à mes chers L2 !
avatar
Azed

Masculin Nombre de messages : 210
Age : 28
Localisation : Lyon
Humeur : La colocation c'est nul !
Date d'inscription : 20/09/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  Azed le Dim 13 Déc 2009 - 17:57

Euh bah finalement non, n*(n+1)/2 ne vaut pas O(n²) (la vraie formule c'est n*(n-1)/2=O(n²) ).

Je comprends vraiment rien à ce truc, je suis désespéré.
avatar
Azed

Masculin Nombre de messages : 210
Age : 28
Localisation : Lyon
Humeur : La colocation c'est nul !
Date d'inscription : 20/09/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  funkyMat le Dim 13 Déc 2009 - 18:26

En effet n*(n+1)/2 et n*(n-1)/2, c'est à peu près pareil. Mais n² non plus, et c'est quand même plus grand que les autres.
On a : n*(n-1)/2 < n*(n+1)/2 < n² mais tout est en O(n²).
Pour l'exam, si tu écris que c'est en O(n*(n+1)/2) soit à peu près O(n²), tu auras tous les points dédiés à la question, ne t'inquiète pas ! Wink
Ne désespère pas pour ça.
En complexité, on cherche juste à trouver un ordre de grandeur au maximum et pas le nombre exact de calcul (qui peut, selon les cas, ne pas être connu a priori, mais uniquement à la fin du traitement).

_________________
"Sans la liberté de blâmer, il n'est point d'éloge flatteur", Beaumarchais
avatar
funkyMat
Admin

Masculin Nombre de messages : 571
Age : 31
Localisation : Marseille 9e
Date d'inscription : 05/06/2008

Voir le profil de l'utilisateur http://matthieu-gorlier.homeip.net

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  Azed le Dim 13 Déc 2009 - 23:07

Ce n'est pas tant le résultat qui me désespère car dans la plus part des cas j'arrive à le trouver. En fait, c'est surtout les justifications que l'on doit fournir qui sont horribles. Parfois, je me retrouve avec des équations récursives affreuses à résoudre quand l'algorithme est en O(nlogn) par exemple.

Je ne sais pas combien de points sont accordés au justifications mais j'espère que ce n'est pas trop élevé parce que sinon je suis cuit.

Sinon je te remercie de ta sollicitude. On peut vraiment compter sur toi.
avatar
Azed

Masculin Nombre de messages : 210
Age : 28
Localisation : Lyon
Humeur : La colocation c'est nul !
Date d'inscription : 20/09/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  funkyMat le Lun 14 Déc 2009 - 16:04

Pour nous, très peu de justifications étaient nécessaires. Il suffisait juste de marquer que, dans ton exemple, tu faisais n fois la boucle for et que tu rappeler récursivement la fonction n-1 fois.
Mais ne t'inquiète pas pour la complexité. Votre cours s'intitule "Algorithmique 1" et pas "Complexité". Wink

_________________
"Sans la liberté de blâmer, il n'est point d'éloge flatteur", Beaumarchais
avatar
funkyMat
Admin

Masculin Nombre de messages : 571
Age : 31
Localisation : Marseille 9e
Date d'inscription : 05/06/2008

Voir le profil de l'utilisateur http://matthieu-gorlier.homeip.net

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  Azed le Mar 15 Déc 2009 - 17:12

C'est vrai.

Mais ne t'inquiètes pas, je ne passe pas non plus mes journées à faire des équations récursives et à calculer des O de je ne sais trop quoi !

Merci encore pour ta sollicitude.
avatar
Azed

Masculin Nombre de messages : 210
Age : 28
Localisation : Lyon
Humeur : La colocation c'est nul !
Date d'inscription : 20/09/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  funkyMat le Jeu 17 Déc 2009 - 20:59

Alors ?
Bien passé ?

_________________
"Sans la liberté de blâmer, il n'est point d'éloge flatteur", Beaumarchais
avatar
funkyMat
Admin

Masculin Nombre de messages : 571
Age : 31
Localisation : Marseille 9e
Date d'inscription : 05/06/2008

Voir le profil de l'utilisateur http://matthieu-gorlier.homeip.net

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  Azed le Lun 21 Déc 2009 - 16:35

Sa peut aller. J'ai juste planté la programmation dynamique parce que je n'ai pas trouvé la bonne formule récursive. J'espère qu'il ne vont pas m'enlever tous les points de cette exo à cause de ça...

Et sinon (petit HS) pour la bioch j'ai trouvé ça vraiment galère. D'autant que cette année les sujets n'avaient plus la même structure que ceux des années précédentes ! Je pense quand même m'en être tiré (au moins la moyenne).

Et vous alors ? Vous en avez eu ? Bien passé ?
avatar
Azed

Masculin Nombre de messages : 210
Age : 28
Localisation : Lyon
Humeur : La colocation c'est nul !
Date d'inscription : 20/09/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  funkyMat le Lun 21 Déc 2009 - 20:34

Nous, rien !
Tout après les vacances Crying or Very sad

_________________
"Sans la liberté de blâmer, il n'est point d'éloge flatteur", Beaumarchais
avatar
funkyMat
Admin

Masculin Nombre de messages : 571
Age : 31
Localisation : Marseille 9e
Date d'inscription : 05/06/2008

Voir le profil de l'utilisateur http://matthieu-gorlier.homeip.net

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  Azed le Lun 21 Déc 2009 - 21:27

Aïe, je compatis pour vous.

Soit dit en passant, il y a des liens morts sur ton site dans les archives de TD de bioinformatique appliquée. Ceci étant dit, nous n'avons plus les mêmes TD car on a changé de prof. Mais j'aurais été curieux de voir ce que vous aviez eu tout de même.

Je suis désolé pour ces HS. ( <- rah... que je l'aime ce smiley !)
avatar
Azed

Masculin Nombre de messages : 210
Age : 28
Localisation : Lyon
Humeur : La colocation c'est nul !
Date d'inscription : 20/09/2008

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: ALGO 1 : complexité

Message  Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum