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 744
    Détails du profil
    Informations forums :
    Inscription : septembre 2010
    Messages : 2 744
    Points : 5 439
    Points
    5 439

    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
    Candidat au Club
    Homme Profil pro
    système
    Inscrit en
    juin 2017
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 21
    Localisation : Congo-Kinshasa

    Informations professionnelles :
    Activité : système

    Informations forums :
    Inscription : juin 2017
    Messages : 5
    Points : 3
    Points
    3

    Par défaut question

    avez vous un cours qui parle sur la complexité des algorithmes?

  4. #4
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 176
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

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

    Informations forums :
    Inscription : août 2008
    Messages : 22 176
    Points : 119 827
    Points
    119 827

    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 ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

    Nouveau ! 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 : 751
    Points
    751

    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
    Ninja
    Inscrit en
    juillet 2013
    Messages
    1 137
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ninja

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 137
    Points : 6 452
    Points
    6 452
    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 030
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 030
    Points : 15 585
    Points
    15 585

    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 Général Algorithmique
    Réponses: 3
    Dernier message: 09/07/2007, 07h27
  2. Complexité de l'algorithme de multiplication de Karatsuba
    Par judge06 dans le forum Général Algorithmique
    Réponses: 4
    Dernier message: 27/03/2007, 12h02
  3. Complexité de l'algorithme de Tri Fusion
    Par judge06 dans le forum Général Algorithmique
    Réponses: 10
    Dernier message: 26/03/2007, 22h04
  4. [Complexité d'un algorithme] Triangle de Sierpinski
    Par Opérateur dans le forum Général Algorithmique
    Réponses: 18
    Dernier message: 18/12/2006, 15h25
  5. complexité d'un algorithme par un...algorithme??
    Par afrikha dans le forum Général Algorithmique
    Réponses: 5
    Dernier message: 02/11/2005, 00h59

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