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¶