none
Opération O(n) RRS feed

  • Question

  • Bonjour tout le monde,

    Dans la documentation de l'objet Stack, est dit quelque part :

    Push devient une opération O(n), où n est égal à Count

    Quelqu'un saurait-il me dire ce que je dois taper dans la zone de saisie d'un moteur de recherche pour savoir ce qu'est une opération O(n) ?

    A défaut, quelle serait la réponse ?

    J'imagine qu'une fois que je saurai ça, je pourrai en déduire ce qu'est une opération O(1).

    dimanche 3 août 2014 09:10

Réponses

  • Bonjour, Une opération en O(n) veut dire que la complexité dépendra d'une variable n. Donc, plus la valeur de n sera grande et plus l'opération prendra du temps. Une opération en o(1) est constante. Elle aura toujours la même complexité quelque soit les variables utilises. Une petit lien pour plus d'explications: http://fr.m.wikipedia.org/wiki/Analyse_de_la_complexité_des_algorithmes Cordialement Cédric
    • Modifié cedric pautet dimanche 3 août 2014 14:16
    • Marqué comme réponse Gloops dimanche 3 août 2014 19:12
    dimanche 3 août 2014 14:12

Toutes les réponses

  • Bonjour, Une opération en O(n) veut dire que la complexité dépendra d'une variable n. Donc, plus la valeur de n sera grande et plus l'opération prendra du temps. Une opération en o(1) est constante. Elle aura toujours la même complexité quelque soit les variables utilises. Une petit lien pour plus d'explications: http://fr.m.wikipedia.org/wiki/Analyse_de_la_complexité_des_algorithmes Cordialement Cédric
    • Modifié cedric pautet dimanche 3 août 2014 14:16
    • Marqué comme réponse Gloops dimanche 3 août 2014 19:12
    dimanche 3 août 2014 14:12
  • Ah OK, merci.

    On pourrait aussi penser à n variables, alors ?

    Le lien à la fin sera bien utile pour comprendre mieux ...

    D'un rapide coup d'œil, il semble que ce soit O comme ordre de grandeur ?

    Je dois bien avouer que c'était la première fois que je voyais utiliser cette expression.

    dimanche 3 août 2014 19:11