4.3: El gran “Oh” y el pequeño “Oh” Notaciones

Última actualización
Guardar como PDF

Page ID: 118464

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Dejar\(f:\mathbb{N} \rightarrow \mathbb{R}\) y\(g:\mathbb{N} \rightarrow \mathbb{R}\) ser funciones. Escribimos\(f=\mathcal{O}(g)\), y decimos\(f\) es “Big Oh” de\(g\), cuando hay una constante\(c\) y un entero\(n_0\) para que\(f(n)≤cg(n)\) cuando sea\(n>n_0\). Aunque esta notación tiene una larga historia, podemos proporcionar una justificación bastante moderna. Si\(f\) y\(g\) ambos describen el número de operaciones requeridas para dos algoritmos dado el tamaño de entrada\(n\), entonces el significado de\(f=\mathcal{O}(g)\) es que no\(f\) es más difícil que\(g\) cuando el tamaño del problema es grande.

Estamos particularmente interesados en comparar funciones con ciertos puntos de referencia naturales, por ejemplo,\(\log⁡ \log⁡ n, \log⁡ n, \sqrt{n}, n^{\alpha}\)\(\alpha<1, n, n^2, n^3, n^c\) dónde\(c>1\) es una constante\(n^{\log⁡n}\),\(2n, n!, 2^{n^2}\),, etc.

Por ejemplo, en la Subsección 3.5.2 aprendimos que existen algoritmos de clasificación con tiempo de ejecución\(\mathcal{O}(n \log⁡ n)\) donde\(n\) está el número de enteros a ordenar. Como segundo ejemplo, aprenderemos que podemos encontrar todos los caminos más cortos en una gráfica orientada sobre\(n\) vértices con pesos no negativos en aristas con un algoritmo que tenga tiempo de ejecución\(\mathcal{O}(n^2)\). En el otro extremo, nadie sabe si existe una constante\(c\) y un algoritmo para determinar si el número cromático de una gráfica es como máximo tres lo que tiene tiempo de ejecución\(\mathcal{O}(n^c)\).

Es importante recordar que cuando escribimos\(f=\mathcal{O}(g)\), estamos insinuando en cierto sentido que no\(f\) es más grande que\(g\), pero de hecho puede ser mucho más pequeño. Por el contrario, habrá momentos en los que realmente sepamos que una función domina a otra. Y tenemos un segundo tipo de notación para plasmar esta relación.

Dejar\(f: \mathbb{N} \rightarrow \mathbb{R}\) y\(g: \mathbb{N} \rightarrow \mathbb{R}\) ser funciones con\(f(n) > 0\) y\(g(n) > 0\) para todos\(n\). Escribimos\(f = \mathcal{o}(g)\), y decimos que\(f\) es “Little oh” de\(g\), cuando\(\lim_{n \to \infty} f(n)/g(n) = 0\). Por ejemplo,\(\ln n = \mathcal{o}(n^{.2})\);\(n^{\alpha} = \mathcal{o}(n^{\beta})\) cuando\(0 < \alpha < \beta\); y\(n^{100} = \mathcal{o}(c^n)\) para cada\(c > 1\). En particular, escribimos\(f(n) = \mathcal{o}(1)\) cuándo\(\lim_{n \to \infty} f(n) = 0\).