Partage
  • Partager sur Facebook
  • Partager sur Twitter

compléxite

    12 mai 2021 à 18:05:11

    Bonjour ! :D 

    il y a quelque temps j'ai eu un contrôle d'algo et même en ayant eu la correction je n'ai pas compris la question suivante :

    On considère la fonction f définie sur N par f(n)=(1/2)n^2-5logn+8 cochez le propositions suivantes :

    - f(n)=O(1)                -f(n)=théta(nlogn)     -f(n)=Omega(n)

    -f(n)=Oméga(n^4)     -f(n)=O(racine(n))     -f(n)=O(n)              

    -f(n)=o(n^2)             -f(n)=théta(n^2)       -f(n)=o(n^3)


    et les réponses étaient f(n)=théta(n^2),f(n)=Omega(n) et f(n)=o(n^3) mais je ne comprend pas pourquoi ?:'( Pouvez-vous m'aider ???


    • Partager sur Facebook
    • Partager sur Twitter
      12 mai 2021 à 19:28:31

      Bonjour,

      voilà l'explication, claire àmha, tirée du Introduction to Algorithms de Cormen, Leiserson, Rivest & Stein :

      Une manière de voir les choses est de se souvenir qu'à partir d'un certain moment on a « 𝚯 encadre parfaitement, 𝚶 est toujours au-dessus mais pas forcément en dessous, et 𝛀 est toujours en dessous mais pas forcément au-dessus».

      Dans ton exemple, f(n) est dominée par n², du coup elle est en 𝚯(n²) (tu prends comme constante 1 et ¼ par exemple), elle n'est pas en O(1) car pour tout nombre k il existe un n tel que f(n)>k, etc …

      • Partager sur Facebook
      • Partager sur Twitter

      compléxite

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