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é et récursivité


Sujet :

Algorithmes et structures de données

  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 : 26
    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 éclairé Avatar de Matthieu76
    Homme Profil pro
    Consultant informatique
    Inscrit en
    Mars 2013
    Messages
    568
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

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

    Informations forums :
    Inscription : Mars 2013
    Messages : 568
    Points : 890
    Points
    890
    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 sénior
    Homme Profil pro
    Responsable Données
    Inscrit en
    Janvier 2009
    Messages
    5 188
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Responsable Données

    Informations forums :
    Inscription : Janvier 2009
    Messages : 5 188
    Points : 12 744
    Points
    12 744
    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 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
    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
    4 038
    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 : 4 038
    Points : 9 347
    Points
    9 347
    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 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 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
    4 038
    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 : 4 038
    Points : 9 347
    Points
    9 347
    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. Cours : algorithmes et récursivité
    Par Community Management dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 17/10/2018, 01h38
  2. Complexité d'uml...?
    Par le Daoud dans le forum Débuter
    Réponses: 5
    Dernier message: 23/12/2004, 19h58
  3. [PS] Récursivité !
    Par maitrebn dans le forum MS SQL Server
    Réponses: 2
    Dernier message: 01/10/2004, 13h18
  4. récursivité
    Par krimson dans le forum PostgreSQL
    Réponses: 12
    Dernier message: 06/05/2004, 16h54
  5. Complexités
    Par victorracine dans le forum Algorithmes et structures de données
    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