Aller au contenu

Complexité d'un programme

  • complexité spatiale , temporelle

  • borne supérieure \(\mathcal{O}(g(n))=\{ f(n):\lvert f(n) \rvert\leq c\lvert g(n) \rvert \quad\forall n>N \}{}\)

    • \(f{}\) appartient :\(f=\mathcal{O}(){}\)
    • \(\mathcal{O}(1)\subset \mathcal{O}(\ln n)\subset \mathcal{O}(n^a)\subset \mathcal{O}(a^n)\subset \mathcal{O}(n!){}\)
  • borne inférieure \(\Omega(g(n))=\{ f(n):\lvert f(n) \rvert\geq c\lvert g(n) \rvert \quad\forall n>N \}{}\)

  • borne exacte : \(\Theta(g(n))=\mathcal{O}(g(n))\cap \Omega(g(n)){}\)
     

  • intrinsequement complexe : \(X\not \in \mathcal{O}(n^a)\)

  • Space complexity : recursive \(\mathcal{O}(n)\) , iterative \(\mathcal{O}(1)\)

Prog - CP

Pasted image 20230926200023.png