1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2015
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

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

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

    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é.

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