1. #1
    Nouveau Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 19
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 1
    Points : 1
    Points
    1

    Par défaut Complexité et récursivité

    Bonjour!
    A l'approche de mes partiels, je suis en train de travailler quelques exercices sur la complexité et je bloque sur quelques un où la complexité est une suite récursive, un peu comme cet exemple-ci:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    function A3(n)
        if n > 1
            return 1 + A3(n-2)*A3(n-2)
        return 0
    En notant T(n) la complexité, j'ai: T(n)=c+T(n-2)2 et ce n'est pas très évident pour moi de trouver un majorant!
    Même chose pour celui-ci: (qui parait un peu plus simple):
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    function A2(n):
        if n > 2
            return 1 + A2(n-3)
        return 1
    Je ne sais pas si je dois trouver une expression de la suite ou simplement essayer de la majorer brutalement, ce qui ne me parait pas très simple non plus.
    Merci d'avance pour votre temps et vos réponses! :)

  2. #2
    Membre habitué Avatar de Matthieu76
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2013
    Messages
    191
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine Maritime (Haute Normandie)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mars 2013
    Messages : 191
    Points : 166
    Points
    166

    Par défaut Petite réponse rapide

    Le temps de complexité pour le premier est :

    (n/2)*2 soit n

    Tu ne parcours que la moitié de n vu que tu fais -2 à chaque fois mais tu le fais 2 fois.
    A3(n)*A3(n) et A3(n)+A3(n) ont le même temps de complexité.


    Et pour le deuxième le temps de complexité est :

    n

    Car tu appelles n fois ta fonction A2
    Bien sûr les constante comme le -3 ne sont pas à prendre en compte car si n = 10 000 le -3 devient négligeable.

  3. #3
    Expert éminent
    Homme Profil pro
    Développeur Freelance
    Inscrit en
    janvier 2009
    Messages
    3 270
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Développeur Freelance

    Informations forums :
    Inscription : janvier 2009
    Messages : 3 270
    Points : 6 908
    Points
    6 908

    Par défaut

    Bonjour,
    C'est bizarre, pour la deuxième j'aurai dit n/3 pour la complexité.
    Par exemple pour n = 15, on appelle A2(15), A2(12), A2(9), A2(6), A2(3).

    C'est le même raisonnement qui donne le n/2 pour A3.
    Ou alors je n'ai rien compris

    Tatayo.

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 039
    Points : 15 615
    Points
    15 615

    Par défaut

    Bonjour,

    Citation Envoyé par tatayo Voir le message
    C'est bizarre, pour la deuxième j'aurai dit n/3 pour la complexité.
    Par exemple pour n = 15, on appelle A2(15), A2(12), A2(9), A2(6), A2(3).

    C'est le même raisonnement qui donne le n/2 pour A3.
    Ou alors je n'ai rien compris
    Tu as raison, c'est le même raisonnement...
    et ce raisonnement nous amène à dire que la complexité en opération est linéaire par rapport à n, c'est à dire de la forme T(n) = a.n+b... donc O(n).

    Faut se rappeler qu'en complexité O(...) on ne cherche pas le nombre exacte d'opérations que l'algo va prendre, mais juste la "forme" de la courbe.
    Dans les deux cas, la forme est une ligne (pas avec la même pente, mais ca reste une ligne).

    Une manière de voir les choses (utile pour les partiels ):

    Split & Merge O(1)
    T(n) = T(n/2) + O(1)    ---> O(log n)
    T(n) = T(n-1) + O(1)    ---> O(n)
    T(n) = 2 T(n/2) + O(1)  ---> O(n)
    
    Split & Merge O(n)
    T(n) = T(n-1) + O(n)    ---> O(n^2)
    T(n) = 2 T(n/2) + O(n)  ---> O(n log n)
    
    Split: La récursion réduit la taille des données à traiter (soit en divisant la taille par une constante, soit en soustrayant une constante à la taille)
    Merge O(1): A chaque étape de la récursion, on doit faire une opération qui ne dépend pas de taille des données (c'est le cas dans tes deux exemples).
    Merge O(n): A chaque étape de la récursion, on doit faire une opération qui dépend linéairement de la taille des donnés (par exemple parcourir les données pour calculer la moyenne)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 510
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 510
    Points : 3 152
    Points
    3 152

    Par défaut

    Ok avec Pseudocode, mais ok aussi avec Tatayo.

    Quand on parle de complexité d'un algorithme, on s'intéresse uniquement à l'exposant qu'on va mettre au dessus de n. Est-ce que c'est n ou n/3, on s'en moque, ce qu'on veut savoir, c'est si c'est n^1, ou n^2 ou n^3, ou n log(n) qu'on retrouve assez souvent.

    Mais dans le message de Matthieu76, mêm si au final, la réponse est juste, il y avait quelques maladresses de formulation.
    Si on dit que le -2 est significatif dans le premie exercice, on ne peut pas dire que le -3 est négligeable dans le 2ème ....

    En particulier, si au lieu de -3, on avait -0, ou +1, la réponse à l'exercice serait très différente !

    Idem, si on avait cet exercice, la réponse serait encore différente.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    function A2(n):
        if n > 2
            return 1 + A2(n*0.97)
        return 1
    Enfin, dans le premier exercice, je pense que la réponse est fausse.
    Je verrais bien une complexité en n²
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 039
    Points : 15 615
    Points
    15 615

    Par défaut

    Citation Envoyé par tbc92 Voir le message
    Enfin, dans le premier exercice, je pense que la réponse est fausse.
    Je verrais bien une complexité en n²
    C'est pire que cela... sur un ensemble de taille 8, par exemple {1,2,3,4,5,6,7,8}
    T({1,2,3,4,5,6,7,8})
    = 2*T({1,2,3,4,5,6})+1
    = 2*(2*T({1,2,3,4})+1)+1
    = 2*(2*(2*T({1,2})+1)+1)+1
    = 2*(2*(2*(2*T({})+1))+1)+1)+1  // T({})=0 car on n'arien à faire.
    = 8+4+2+1
    = 15
    
    Le terme général est T(n) = 2^(n/2) - 1
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 510
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 510
    Points : 3 152
    Points
    3 152

    Par défaut

    Oui, bien sûr ! 2x2x2x2 .. et non NxN !
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

Discussions similaires

  1. Complexité d'uml...?
    Par le Daoud dans le forum Débuter
    Réponses: 5
    Dernier message: 23/12/2004, 19h58
  2. [PS] Récursivité !
    Par maitrebn dans le forum MS SQL-Server
    Réponses: 2
    Dernier message: 01/10/2004, 13h18
  3. récursivité
    Par krimson dans le forum PostgreSQL
    Réponses: 12
    Dernier message: 06/05/2004, 16h54
  4. Cours : algorithmes et récursivité
    Par Community Management dans le forum Général Algorithmique
    Réponses: 0
    Dernier message: 07/02/2003, 17h49
  5. Complexités
    Par victorracine dans le forum Général Algorithmique
    Réponses: 29
    Dernier message: 07/09/2002, 17h13

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