Répondre à la discussion
Affichage des résultats 1 à 7 sur 7

Calcul de Complexité




  1. #1
    lilipletz

    Calcul de Complexité

    Bonsoir, je cherchais à approfondir mes connaissances jusqu'ici très basiques en calcul de complexité et voilà que je me heurte à un roc (que dis-je un roc... une péninsule) plus haut et bien plus costaud que ma personne :

    T(n) = 2 * T(3*(n/4)) + T(n/4) + n

    J'avoue que je ne sais pas par où attaquer des complexités avec des équations de récurrences, si quelqu'un pouvait me donner un tuyau afin de savoir par où commencer.

    Merci d'avance,

    Lilipletz

    -----


  2. Publicité
  3. #2
    lilipletz

    Re : Calcul de Complexité

    Donc mon idée principale était :

    T(n) = a * T(n/b) + cn

    Je sais que :

    If a=b : T(n) = O(n.logn)
    If a<b and c>0 : T(n) = O(n)
    If a<b and c=0 : T(n) = O(logn)
    If a>b : T(n) = O(nlogb(a))

    J'écris T(n) = 2 T( n/(4/3)) + n + T(n/4)

    a > b so T(n) = O(nlogb(a)) with a = 2 and b = 4/3

    Donc il reste :
    T(n) = O(nlog4/3(2)) + T(n/4)

    De la même manière en m'occupant de T(n/4) , je trouve O(log(n))

    Ce qui me laisserait donc avec une complexité de O(log(n)) + O(nlog4/3(2)) ??

  4. #3
    JPL

    Re : Calcul de Complexité

    Quel est ton problème ? Mathématique ou programmation ?
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac


  5. #4
    lilipletz

    Re : Calcul de Complexité

    Bonjour,
    Merci de votre réponse

    J'imagine un peu les deux, je ne vois pas si je choisis la bonne démarche pour trouver la complexité de cette equation de récurrence

  6. #5
    lilipletz

    Re : Calcul de Complexité

    Personne ?

  7. A voir en vidéo sur Futura
  8. #6
    JPL

    Re : Calcul de Complexité

    Veux-tu que je déplace ton sujet en Mathématiques du supérieur ?
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac

  9. #7
    lilipletz

    Re : Calcul de Complexité

    Volontiers, j'imagine qu'il y trouvera sa place =)

  10. Publicité

Discussions similaires

  1. Mesure de la complexité
    Par BillyNut's dans le forum Chimie
    Réponses: 0
    Dernier message: 08/06/2015, 00h11
  2. Complexité en O(log n)
    Par Fankouik dans le forum Programmation et langages, Algorithmique
    Réponses: 0
    Dernier message: 21/01/2015, 00h13
  3. Complexité
    Par banzkura dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 14/01/2014, 19h00
  4. Complexité Temps
    Par kin21 dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 13/11/2011, 19h39
  5. Complexité
    Par isozv dans le forum Mathématiques du supérieur
    Réponses: 26
    Dernier message: 10/12/2004, 20h58