Entiendo matemáticamente $ f (n) \ in O (g (n)) $: $ f (n) $ no crecer más rápido que $ g (n) $. Más formalmente, $ \ existe c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
De manera similar, $ f (n) \ in \ Theta (g (n)) $ significa que $ f (n) $ crece aproximadamente tan rápido como $ g (n) $. es decir, $ f (n) \ in O (g (n)), \ Omega (g (n)) $.
Lo que no entiendo es por qué la gente usa big Oh para el tiempo de ejecución de ¿Un algoritmo? ¿No deberíamos usar Big Theta? Cuando decimos «Tiempo de ejecución» de un algoritmo, nos referimos al tiempo de ejecución del peor caso, es decir, $ T (n) = max \ {ALG (x): | x | = n \} $.
Por ejemplo: el peor tiempo de ejecución de una búsqueda lineal en una entrada de tamaño $ n $ ($ n $ elementos y un valor objetivo) es $ \ Theta (n) $ y $ O (n) $, pero $ \ Theta (n) $ da más información. Entonces, ¿por qué los libros de algoritmos usan $ O (n) $ y no $ \ Theta (n) $.
Comentarios
- A menudo ‘ s porque simplemente no podemos ‘ t obtener un límite estrecho de big theta en el tiempo de ejecución de un algoritmo. Si un algoritmo es lo suficientemente complicado, puede suceder que lo mejor que podamos hacer es decir que el tiempo de ejecución es, digamos $ O (n ^ {n!}) $ Donde en realidad podría ser $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Razones históricas.
- » Lo que no hago ‘ ¿Por qué la gente usa Big Oh para el tiempo de ejecución de un algoritmo? Si no ‘ usaremos Big Theta. » – Sí. Espera, no, deberíamos hacer declaraciones aún más precisas. Pero si tengo que elegir, sí, $ \ Theta $!
Responder
Veo dos razones por las que la gente prefiere Big Oh sobre Big Theta:
- La complejidad del tiempo de ejecución de un algoritmo no necesariamente se define como la complejidad del tiempo de ejecución del peor de los casos. También puede verlo como el tiempo de ejecución en una instancia arbitraria de longitud $ n $. Entonces, si escribe, por ejemplo, que el tiempo de ejecución $ t (n) $ de un algoritmo está en $ \ mathcal {O} (n ^ 2) $, esto significa que cualquier entrada de longitud $ n $ que elija, siempre crecerá asintóticamente más lento que la función $ c \ cdot n ^ 2 $ para algunos $ c $ constantes, por lo que obviamente estamos haciendo una declaración sobre el peor tiempo de ejecución.
- A veces, cuando analizas el tiempo de ejecución complejidad de un algoritmo que no sabe con certeza si la complejidad del peor de los casos que está dando es muy ajustada. Tomemos, por ejemplo, la complejidad en tiempo de ejecución de la multiplicación de matrices . Todavía no está claro si el tiempo de ejecución $ n ^ {2.3728639} $ es realmente el peor de los casos. Y por lo tanto, se sabe que el tiempo de ejecución está en $ \ mathcal {O} (n ^ {2.3728639}) $ mientras » No estoy seguro si está en $ \ Theta (n ^ {2.3728639}) $.
Pero también, tiene razón en que en algunos casos sería mejor proporcionar un Big Theta límite que un límite de Big Oh.
Comentarios
- Anuncio 1: Lectores, tengan cuidado para no leer demasiado en eso !
Responder
Un límite superior (descuidado) es más fácil de demostrar que un límite superior ajustado, y mucho menos los límites superiores e inferiores.
El tiempo de ejecución de algún algoritmo no puede «t darse con la misma función que el límite superior / inferior. P.ej. Los algoritmos de ordenación simples son $ O (n ^ 2) $, pero tienen un límite inferior $ \ Omega (n) $.
Algunos insisten en esforzarse por dar rendimiento en términos asintóticos a través de $ \ sim $, donde $ f (n) \ sim g (n) $ si
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(digamos como un promedio, o el peor de los casos, en términos de número de alguna operación crítica, como comparaciones al ordenar). Es decir, margen de maniobra, pero no hay constantes (posiblemente enormes) escondidas debajo de la alfombra.
Comentarios
- Cuando nos referimos a » runtime «, nos referimos a algo como tiempo de ejecución en el mejor de los casos, tiempo de ejecución en el peor de los casos y tiempo de ejecución promedio en el caso. Por ejemplo: Quicksort tiene $ \ Theta (n ^ 2) $ tiempo de ejecución en el peor de los casos y $ \ Theta (n) $ en el mejor tiempo de ejecución. Las asintóticas se definen en las funciones a la derecha.
Respuesta
Si se puede usar big-Theta en lugar de big- Oh, debería usarse a menos que agregue una dificultad innecesaria para la comprensión. Hay algunos casos sutiles en los que big-Theta no se puede usar en lugar de big-Oh, por ejemplo:
Considere el siguiente problema: ordenar matrices de longitud uniforme. El programa para resolver este problema podría ser: si la longitud de la matriz es impar, salga inmediatamente, si la longitud de la matriz es par, realice la clasificación de burbujas. ¿Cuál es el peor tiempo de ejecución de este algoritmo?
Seguramente es $ O (n ^ 2) $, pero NO es $ \ Omega (n ^ 2) $ en el sentido $ \ Generalmente se define Omega $. En cambio, su peor tiempo de ejecución es «$ \ Omega (n ^ 2) $ infinitamente a menudo», por así decirlo (advertencia: terminología no estándar).
Respuesta
En la respuesta de «¿por qué los libros de algoritmos usan big-Oh y no Theta»:
Big-Oh se usa para el análisis del peor de los casos y Big-Omega se usa solo para el mejor de los casos. Pero analizando en términos de Big-Theta, hablamos de Big-Oh & Big-Omega simultáneamente.
es decir. Para Big-Theta es necesario que Big-Oh == Big-Omega, de lo contrario no podemos hablar de Big-Theta.
Entonces, donde sea que (libro / cualquier documento) vea el uso de Big-Theta, están dando la complejidad de ambos Big-Oh & Big-Omega (y ambos son iguales también). Pero en muchos casos no son iguales, entonces solo usamos Big- Oh, solo para el peor de los casos.