ALGO 1 : complexité

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!!!

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 !

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.

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

Oki @ demain.

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.

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

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 !

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é.

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 !
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).

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.

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é".

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.

Alors ?
Bien passé ?

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é ?

Nous, rien !
Tout après les vacances

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 !)