Entendiendo la definición de la notación big-O

Question

En un libro de texto, me encontré con una definición de big-oh notación, se va como sigue:

Decimos que $f(x)$ $O(g(x))$ si hay constantes $C$ $k$ tal que $$|f(x)| \le C|g(x)|$$ whenever $x \gt k$.

Si no me equivoco, básicamente, esto se traduce a: $$f(x) = O(g(x)) \Leftarrow\Rightarrow (\exists C,\exists k|C,k \epsilon \Bbb R \land (x \gt k \rightarrow |f(x)| \le C|g(x)|))$$ Ahora, tengo dos preguntas sobre esta declaración:

1. Es mi detallado de la traducción correcta?

2. ¿Qué significa exactamente esta definición de big-oh notación media sobre el uso de big-oh notación, porque por lo que puedo entender a través de la informática, big-oh se utiliza para representar la complejidad computacional de un algoritmo. Entonces, ¿cómo se relaciona esto con la complejidad de un algoritmo (en todo caso)?

Answer 1

Su traducción es correcta. La intuición detrás de las grandes-oh notación es que $f$ $O(g)$ si $g(x)$ crece tan rápido o más rápido de lo $f(x)$$x \rightarrow \infty$. Este es utilizado en la informática siempre que el estudio de la época de la complejidad de un algoritmo. Específicamente, si dejamos $f(n)$ ser el tiempo de ejecución (número de pasos) que un algoritmo tiene una $n$ bits de entrada para dar una salida, entonces puede ser útil decir algo como $f$$O(n^2)$, de modo que sabemos que el algoritmo es relativamente rápido para grandes entradas de $n$. Por otro lado, si todo lo que sabía era $f$$O(2^n)$, $f$ podría correr demasiado lento para grandes entradas.

Nota digo "podría" aquí, dado que el big-oh, sólo le da un límite superior, por lo $n^2$ $O(2^n)$ pero $2^n$ no $O(n^2)$.

Answer 2

Sí, tu traducción detallada es correcta.

La definición esencialmente indica que la notación Big-Oh es una herramienta para denotar un límite superior para una función. Es decir, si$f(x)$ es$\mathcal{O}(2^x)$, eso significa que, más allá de algún punto, un múltiplo constante de$2^x$ siempre será mayor que$f(x)$.

Esto se usa en ciencias de la computación para indicar que, a largo plazo, solo podemos asumir que se necesitan$2^x$ operaciones para realizar el algoritmo (porque está lo suficientemente cerca).