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