Partage
  • Partager sur Facebook
  • Partager sur Twitter

Complexité exponentielle

Exemple du cours de complexité algorithmique

    11 novembre 2022 à 15:41:38

    Hello,

    Pourquoi dans le cours de complexité exponentielle il est  ecrit 103 iterations (10*10*10) ca fait mille et pas 103 ou alors j'ai pas compris le concept d'iteration ou je calcul mal est ce que quelqu'un peut m'expliquer?

    merci

    • Partager sur Facebook
    • Partager sur Twitter
      16 novembre 2022 à 13:48:20

      Bonjour,

      je pense qu'il s'agit d'un typo ; il faut lire 10^3 ou 10³ au lieu de 103 … note que O(10³) = O(1), cet algo est même en Θ(1).

      • Partager sur Facebook
      • Partager sur Twitter
        17 novembre 2022 à 15:44:22

        L'exemple est mal choisi, 103 et 10^3 étant des constantes, ça revient au même. La complexité c'est une histoire de comparaison d'asymptotes.

        Ca aurait un sens avec 3 boucles imbriquées exécutées chacune N fois. Là on pourrait s'intéresser à O(N^3), qui grandit comme le cube de N quand celui-ci tend vers l'infini.

        -
        Edité par michelbillaud 19 novembre 2022 à 8:13:54

        • Partager sur Facebook
        • Partager sur Twitter

        Complexité exponentielle

        × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
        • Editeur
        • Markdown