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é d'un algorithme (notation grand O)


Sujet :

Algorithmes et structures de données

  1. #1
    Futur Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Novembre 2015
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : Novembre 2015
    Messages : 4
    Points : 5
    Points
    5
    Par défaut Complexité d'un algorithme (notation grand O)
    Salut,
    En math on dit que f(n) est O(g(n)) si f(n)<=g(n)*c pour tout n>n0.


    Donc si un algorithme a 3n+1 opérations, dans ce cas on dit que ca complexité est O(n),
    pour pour que ca soit vrai il faut que 3n+1<=n*c

    Concrètement , la constante 'c' représente quoi en informatique? car je vois que 3n+1 est tjr > n,et si j'ajoute la constante 'c' j’aimerai savoir ce qu'elle est

    Merci .

  2. #2
    Expert confirmé Avatar de DonQuiche
    Inscrit en
    Septembre 2010
    Messages
    2 741
    Détails du profil
    Informations forums :
    Inscription : Septembre 2010
    Messages : 2 741
    Points : 5 485
    Points
    5 485
    Par défaut
    Bonjour.

    C'est une constante arbitraire, elle ne nous intéresse pas et nous ne cherchons pas à l'évaluer. Il suffit qu'il existe un nombre fini quelconque satisfaisant l'équation.

    En effet ce qui nous intéresserait réellement c'est l'évaluation du temps de calcul par rapport aux données du problème. Mais ce temps de calcul est impossible à évaluer précisément ainsi et sans considérer l'architecture matérielle en détail (ce qui n'est fait, je crois, que pour des applications critiques comme l'aéronautique), et il serait difficile de raisonner avec une telle modélisation.

    A la place nous nous bornons donc à évaluer la complexité, qui nous servira à caractériser le comportement en fonction de la taille des données sur une machine idéale. Ce qui nous intéresse c'est uniquement la classe (polynomiale, exponentielle, factorielle, etc) et le dégré (du polynôme par ex). O(n) ? O(n^2) ? O(exp(n)) ? C'est largement plus important que de savoir si c vaut 3 ou 4, d'autant que cette constante ne représenterait pas la réalité.

  3. #3
    Membre à l'essai
    Homme Profil pro
    système
    Inscrit en
    Juin 2017
    Messages
    18
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 28
    Localisation : Congo-Kinshasa

    Informations professionnelles :
    Activité : système

    Informations forums :
    Inscription : Juin 2017
    Messages : 18
    Points : 13
    Points
    13
    Par défaut question
    avez vous un cours qui parle sur la complexité des algorithmes?

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 609
    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 : 26 609
    Points : 188 582
    Points
    188 582
    Par défaut
    Pas mal de cours sur https://algo.developpez.com/cours/ en parlent. Maintenant, si tu veux une approche plus mathématique, tu peux regarder du côté de https://fr.wikipedia.org/wiki/Th%C3%...h%C3%A9orique) — mais c'est le niveau supérieur à la notation O, ça te permettra peut-être de relativiser la faible utilité des constantes et autres termes dominés.
    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 !

  5. #5
    Membre éclairé
    Homme Profil pro
    Ingénieur R&D en apprentissage statistique
    Inscrit en
    Juin 2009
    Messages
    447
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur R&D en apprentissage statistique

    Informations forums :
    Inscription : Juin 2009
    Messages : 447
    Points : 752
    Points
    752
    Par défaut
    @davidbenda Je te conseille "Introduction à l'algorithmique" de Thomas Cormen, les concepts sont très bien expliqués.

  6. #6
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    Citation Envoyé par fil1990 Voir le message
    Salut,
    En math on dit que f(n) est O(g(n)) si f(n)<=g(n)*c pour tout n>n0.


    Donc si un algorithme a 3n+1 opérations, dans ce cas on dit que ca complexité est O(n),
    pour pour que ca soit vrai il faut que 3n+1<=n*c

    Concrètement , la constante 'c' représente quoi en informatique? car je vois que 3n+1 est tjr > n,et si j'ajoute la constante 'c' j’aimerai savoir ce qu'elle est

    Merci .
    La notation O(n) considère comme équivalent un programme A (de tri par exemple) qui s'exécuterait en n instructions, d'un autre programme B qui s'exécuterait en 2n instructions, où n étant la quantité de données à traiter.

    Ça peut paraître bizarre au début, mais en fait pas tant que ça. L'idée est de faire abstraction de la machine qui fait tourner les programmes. Dans notre exemple, le programme B n'aura besoin que de s'exécuter sur une machine 2 fois plus rapide pour avoir le même temps d'exécution que le programme A.

    Quand le nombre d'instructions à exécuter entre deux programmes diffère d'un facteur constant c, on considère que ces deux programmes sont de la même classe de complexité algorithmique. Si on est capable de faire tourner l'un, on peut raisonnablement penser pouvoir faire tourner l'autre. C'est ce que signifie cette constante c. Même si un programme B s'exécute en 2 fois ou 3 fois plus d'instructions qu'un programme A, à quantité de données à traiter égale, nous avons à notre disposition des moyens extérieurs au programme pour rendre leur temps d'exécution équivalent : améliorer la machine.

    Par contre, il existe des programmes qui même en améliorant la machine ne permettront pas d'obtenir des temps d'exécution dit raisonnables pour de grandes valeurs de n. On parle de complexité polynomiale (encore que ce n'est pas exact puisque ça reste encore des programmes théoriquement à notre portée) et de complexité exponentielle. Dans le cas d'un problème nécessitant un programme de complexité exponentielle, la quantité de données à traiter fait rapidement exploser le nombre d'instructions à exécuter. L'exemple le plus courant est celui du voyageur de commerce.

    Dans ce cas, la seule solution raisonnable pour résoudre le problème associé au programme, c'est d'optimiser/changer l'algorithme pour réduire la complexité algorithmique. Par exemple, remplacer un tri à bulle de complexité O(n²) en un tri fusion en O(n.log(n)).
    Tutoriels et FAQ TypeScript

  7. #7
    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 yahiko Voir le message
    La notation O(n) considère comme équivalent un programme A (de tri par exemple) qui s'exécuterait en n instructions, d'un autre programme B qui s'exécuterait en 2n instructions, où n étant la quantité de données à traiter.

    Ça peut paraître bizarre au début, mais en fait pas tant que ça. L'idée est de faire abstraction de la machine qui fait tourner les programmes. Dans notre exemple, le programme B n'aura besoin que de s'exécuter sur une machine 2 fois plus rapide pour avoir le même temps d'exécution que le programme A.
    C'est aussi l'explication que je me faisais de la complexité...
    et puis j'ai eu un prof d'algo qui m'a présenté cela sous la forme de classes de domination asymptotique:

    • il y a la classe des dominants: "f domine g" <=> "f()/g() --> +oo"
    • il y a la classe des dominés: "f est dominé par g" <=> "f()/g() --> 0"
    • il y a la classe "ni l'un ni l'autre": "f est équivalent à g" <=> "f()/g() --> constante située quelque part entre 0 et +oo"
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. Complexité de l'algorithme de multiplication matricielle de strassen
    Par judge06 dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 09/07/2007, 08h27
  2. Complexité de l'algorithme de multiplication de Karatsuba
    Par judge06 dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 27/03/2007, 13h02
  3. Complexité de l'algorithme de Tri Fusion
    Par judge06 dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 26/03/2007, 23h04
  4. [Complexité d'un algorithme] Triangle de Sierpinski
    Par Opérateur dans le forum Algorithmes et structures de données
    Réponses: 18
    Dernier message: 18/12/2006, 16h25
  5. complexité d'un algorithme par un...algorithme??
    Par afrikha dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 02/11/2005, 01h59

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