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 :

Calcul de complexité


Sujet :

Algorithmes et structures de données

  1. #21
    Membre habitué
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    65
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 65
    Points : 179
    Points
    179
    Par défaut
    Citation Envoyé par antares56 Voir le message
    Ok donc si j'ai compris la méthode:
    pour celle là
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    int f(int [] t){
    int j=t.length * t.length;
    return j;
    }
    C'est du O(1) (car opération élémentaire)
    Oui¹


    Citation Envoyé par antares56 Voir le message
    pour celle là
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    void f(int [] t){
    int i=t.length-1;
    while(i<t.length && i>0){
    if (t[i]>=0 && t[i]<t.length){
    i=t[i];
    } else { i=0; }
    }
    }
    C'est du O(N)
    mmm … comment dire ... pourquoi n'essayes-tu pas de faire une trace pour te donner une idée … par exemple avec t={0} ou t={5,4,3,2,1,0} ou t={10,20,30} …

    Citation Envoyé par antares56 Voir le message
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    void f(int [] t){
    int m= t.length;
    int res= 0;
    while (m>0){
    m=m/2;
    res=res+1;
    }
    }
    Et celle là du O(1) aussi ?
    à nouveau il faut faire une trace pour se faire une idée ; mais basiquement on se dit que ça va surtout dépendre de la valeur de m qui influe sur le nombre de tour de boucles, et de quoi dépend la valeur de m ?



    ¹: on part du principe que l'accès à la donnée t.length se fait en temps constant évidemment. Cela est courant lorsqu'il s'agit d'un tableau ; mais il faut faire attention car ce n'est absolument pas le cas pour d'autres sdd classiques comme les listes simplement chaînée par exemple.

  2. #22
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2020
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Morbihan (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2020
    Messages : 39
    Points : 13
    Points
    13
    Par défaut
    Pour la 2 si j'essaye avec le t = {10,20,30};
    i = 2
    donc le while est valide on passe au if
    si t[2] > = 0 && t[2]<t.length) donc le if n'est pas valide car t[2] n'est pas plus grand que t.length
    ensuite on va direct dans le else et donc i sera égal à 0. Donc en faites c'est comme si tu faisais des opérations élémentaires non? Donc c'est O(1)?

    m dépend de t.length mais on fait quand même des opérations basiques, donc à part O(1) je vois pas

  3. #23
    Membre habitué
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    65
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 65
    Points : 179
    Points
    179
    Par défaut
    Citation Envoyé par antares56 Voir le message
    Pour la 2 si j'essaye avec le t = {10,20,30};
    i = 2
    donc le while est valide on passe au if
    si t[2] > = 0 && t[2]<t.length) donc le if n'est pas valide car t[2] n'est pas plus grand que t.length
    ensuite on va direct dans le else et donc i sera égal à 0. Donc en faites c'est comme si tu faisais des opérations élémentaires non? Donc c'est O(1)?
    Et avec les autres tableaux ?

    Citation Envoyé par antares56 Voir le message
    m dépend de t.length mais on fait quand même des opérations basiques, donc à part O(1) je vois pas
    Est-ce qu'avec un tableau deux fois plus grand l'exécution prendra plus ou moins de temps ?

  4. #24
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2020
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Morbihan (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2020
    Messages : 39
    Points : 13
    Points
    13
    Par défaut
    Citation Envoyé par WhiteCrow Voir le message
    Et avec les autres tableaux ?
    pour t{0} il se passe absolument rien et pour t={5,4,3,2,1,0};:
    donc i = 5;
    le while est bon donc passe à la boucle suivante:
    le if est bon donc on passe à la boucle suivante
    donc i prend la valeur t[5] donc i = 0;
    et le programme finit ici




    Est-ce qu'avec un tableau deux fois plus grand l'exécution prendra plus ou moins de temps ?


    Plus de temps puisqu'il y aura plus de divisions à faire

  5. #25
    Membre habitué
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    65
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 65
    Points : 179
    Points
    179
    Par défaut
    Citation Envoyé par antares56 Voir le message
    pour t{0} il se passe absolument rien et pour t={5,4,3,2,1,0};:
    donc i = 5;
    le while est bon donc passe à la boucle suivante:
    le if est bon donc on passe à la boucle suivante
    donc i prend la valeur t[5] donc i = 0;
    et le programme finit ici
    Et un tableau du genre t[]={0,1} ?

    Citation Envoyé par antares56 Voir le message
    Plus de temps puisqu'il y aura plus de divisions à faire
    Tu es donc en train de me dire que le temps n'est pas constant … donc que la complexité n'est pas en O(1) …

  6. #26
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2020
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Morbihan (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2020
    Messages : 39
    Points : 13
    Points
    13
    Par défaut
    Citation Envoyé par WhiteCrow Voir le message
    Et un tableau du genre t[]={0,1} ?
    i=1;
    le while est bon
    if est bon aussi
    du coup i = 1
    du coup ça tourne en boucle



    Tu es donc en train de me dire que le temps n'est pas constant … donc que la complexité n'est pas en O(1) …[/QUOTE]

    Ok donc étant donné que plus le tableau est grand plus il y a de divisions, c'est en log2(n)?

  7. #27
    Membre habitué
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    65
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 65
    Points : 179
    Points
    179
    Par défaut
    Citation Envoyé par antares56 Voir le message
    i=1;
    le while est bon
    if est bon aussi
    du coup i = 1
    du coup ça tourne en boucle
    Oui, par définition un algorithme doit toujours finir en un nombre fini d'étapes. Ce qui n'est pas le cas ici, il ne s'agit pas d'un algorithme, tu ne peux donc pas en déterminer la compléxité (qui ne dépend pas de la taille de l'entrée mais du contenu de l'entrée ce qui est très différent).

    Citation Envoyé par antares56 Voir le message
    Tu es donc en train de me dire que le temps n'est pas constant … donc que la complexité n'est pas en O(1) …
    Ok donc étant donné que plus le tableau est grand plus il y a de divisions, c'est en log2(n)?[/QUOTE]

    Je sais pas ... comment peux-tu le prouver ?

  8. #28
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2020
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Morbihan (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2020
    Messages : 39
    Points : 13
    Points
    13
    Par défaut
    Citation Envoyé par WhiteCrow Voir le message
    Oui, par définition un algorithme doit toujours finir en un nombre fini d'étapes. Ce qui n'est pas le cas ici, il ne s'agit pas d'un algorithme, tu ne peux donc pas en déterminer la compléxité (qui ne dépend pas de la taille de l'entrée mais du contenu de l'entrée ce qui est très différent).



    Ok donc étant donné que plus le tableau est grand plus il y a de divisions, c'est en log2(n)?
    Je sais pas ... comment peux-tu le prouver ?[/QUOTE]

    Parce que quand c'est logarithmique on peut voir grâce au graphe que la courbe n'augmente pas considérablement comme une constante ou en quadratique par exemple

  9. #29
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 611
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 611
    Points : 11 515
    Points
    11 515
    Par défaut
    Arrêtez le carnage. antares56, tu ne trouves pas, car tu ne sais pas ce que tu cherches. C'est quoi la complexité algorithmique ? C'est essayer de répondre à la question "Si j'ai plus de clients, ai-je plus de travail pour les satisfaire ?". Si tu es coiffeur, oui. Ton travail de coiffeur augmente proportionnellement à ton nombre de clients. Mais si tu acteur de théâtre, non. Tu joues le même texte, une seule fois, que tu aies 20 spectateurs ou 150 spectateurs. La complexité du coiffeur est O(n) et celle de l'acteur O(1). On peut donc avoir pour complexité 1, n, n², n³, n⁴, etc, ln(n), exp(n) et leurs composés. Le critère important est la croissance comparée. Car tu peux très bien trouver une parabole (n²) qui passe par-dessus une exponentielle. 3n²+6 > 2exp(n) si n=0. Mais si n augmente, à l'infini, l'exponentielle sera toujours au dessus de ta parabole. Voilà pourquoi on dit que l'exponentielle croît plus vite qu'un polynôme.

    Maintenant, dans tes bouts de code, si ton tableau en entrée est 10 fois plus grand, le travail sera-t-il 10 fois plus long ? 100 fois plus long ? 1000 fois plus long ? Constant ? Quelle est la formule en fonction de n ?

    Note : la proportionnalité n'est pas obligatoire. Si, pour chaque client, tu donnes les coordonnées de tous les autres clients, tu auras n*n=n² opérations. Car pour chaque clients (n contextes), tu devras rechercher les coordonnées de chaque client (n opérations).
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  10. #30
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2020
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Morbihan (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2020
    Messages : 39
    Points : 13
    Points
    13
    Par défaut
    Merci pour ta réponse déjà, mais par contre j'ai été clair dès le début, j'ai été transparent sur le fait que je n'avais pas la technique et que justement je suis venu ici pour que l'on m'explique le fonctionnement ,(ce que WhiteCrow a fait avec ses mots et je l'en remercie), y'a t'il une sorte de cours sur ce site sur la complexité? (je suis assez nouveau ici je sais pas trop où chercher )

  11. #31
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    25 857
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 25 857
    Points : 181 642
    Points
    181 642
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

Discussions similaires

  1. Calcul de complexité
    Par zizo08 dans le forum MATLAB
    Réponses: 13
    Dernier message: 25/11/2008, 21h43
  2. calcul de complexité fonction mathematique
    Par abdelhamidem dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 16/05/2008, 14h37
  3. calcul de complexité itératif ou algorithmique
    Par miltone dans le forum Algorithmes et structures de données
    Réponses: 13
    Dernier message: 08/04/2008, 19h38
  4. calcul de complexité
    Par an1981 dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 10/02/2008, 16h26
  5. Calcul de complexité
    Par sandytarit dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 20/11/2007, 19h37

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