Solución:
Para una función f(n), g(n) es un límite superior (O grande) si para “n suficientemente grande”, f(n)<=c*g(n), por una constante c. [g dominates f]
g (n) es límite inferior (gran Omega) si para “n suficientemente grande”, f(n) >= c*g(n), por una constante c. [f dominates g]
Si g(n) es tanto el límite superior como el límite inferior de f(n) [with different c’s], decimos que g (n) es un límite estrecho para f (n) [Big theta]
Utilice un ejemplo para el límite superior en lugar de uno estrecho: algunas veces es difícil encontrar un límite ajustado, como para el algoritmo recursivo de fibonacci. entonces encontramos un límite superior fácil de O (2 ^ n), fácilmente. se encuentra más información en las respuestas de esta publicación.
¿Cómo se relaciona con los casos peores / básicos / …? (según lo solicitado por los comentarios):
El peor caso / caso promedio (o cualquier otro caso) está afectando cuál es la función de complejidad, pero cada uno de big-O, big-Omega y big-Theta se pueden aplicar a cada uno de estos casos.
Por ejemplo, una inserción HashTable, es Theta(1) inserción de caso promedio, y Theta(n) inserción en el peor de los casos. Tambien es O(n) inserción de caso promedio (el límite no es estricto), y Omega(1) inserción en el peor de los casos.
Primero, hablemos de casos. A caso de aporte por un algoritmo está asociado con un ejemplo de un problema. Para el problema de clasificación (donde queremos encontrar una permutación de un conjunto en un orden específico), puedo mirar una instancia como el conjunto de números {1, 5, 4, 2, 6}. Este conjunto de números sería la entrada a un algoritmo de clasificación que pretende resolver el problema de clasificación, como la clasificación por selección, o uno de los otros algoritmos de clasificación que existen.
Se pueden proporcionar los mismos conjuntos de entradas a cualquier algoritmo que desee resolver un problema. No importa qué algoritmo de clasificación utilice, el conjunto de entradas es siempre el mismo (porque, por definición, todas son instancias del mismo problema). Sin embargo, un caso dado puede ser mejor o peor para un algoritmo dado. Algunos algoritmos siempre funcionan igual sin importar cuáles sean las entradas, pero algunos algoritmos pueden funcionar peor en algunas entradas. Sin embargo, esto significa que cada algoritmo tiene el mejor de los casos y el peor de los casos; a veces también hablamos del caso promedio (tomando el promedio de todos los casos) o del caso esperado (cuando tenemos alguna razón para esperar que un caso sea más común que otros).
Ejemplos de casos de algoritmos
El problema de “encontrar el mínimo de una lista no ordenada” siempre funciona igual para todas las entradas posibles. No importa qué algoritmo inteligente escriba, debe verificar cada elemento. No importa si tienes una lista de ceros o una lista de números aleatorios o una lista donde el primer elemento es el mínimo, no lo sabes hasta que llegas al final. Todos los casos son iguales para ese algoritmo, por lo que el mejor de los casos es el peor de los casos, y también el caso promedio y el caso esperado. Si la lista estuviera ordenada, podríamos hacerlo mejor, pero ese es un problema diferente.
El problema de “encontrar un elemento dado en una lista” es diferente. Suponiendo que estaba usando un algoritmo que hace un recorrido lineal a través de la lista, podría resultar que el elemento dado fuera el primer elemento de la lista y ya está listo de inmediato. Sin embargo, también podría ser el último elemento de la lista, en cuyo caso debe recorrer todo antes de encontrarlo. Así que ahí tenías el mejor de los casos y el peor de los casos.
Algoritmos como funciones del tamaño de entrada
Cuando queremos analizar un algoritmo, los algoritmos pensamos en todos los casos posibles que podríamos lanzar al algoritmo. Por lo general, los dos casos más interesantes son el mejor y el peor de los casos. Si piensa en el tiempo de ejecución de los algoritmos como una función de su entrada, el mejor caso es la entrada que minimiza la función y el peor caso es la entrada que maximiza la función. Estoy usando “función” en el sentido matemático de Álgebra aquí: una serie de pares x / y (pares de entrada / salida, o en este caso “tamaño de entrada / número de pasos de ejecución”) que dibujan una línea.
Debido a que el tiempo de ejecución de los algoritmos es una función de su entrada, tenemos un mejor caso (y el peor de los casos) diferente para cada tamaño de entrada posible. Entonces, a veces tratamos el mejor caso como una sola entrada, pero en realidad es un conjunto de entradas (una para cada tamaño de entrada). El mejor y el peor de los casos son cosas muy concretas con respecto a un algoritmo dado.
Límites
Ahora, ¿qué pasa con los límites? Los límites son funciones que usamos para comparar con la función de un algoritmo dado. Hay un número infinito de funciones de contorno que podríamos considerar. ¿Cuántos tipos posibles de líneas puedes dibujar en una gráfica? Esa es la cantidad de funciones de límite que hay. La mayoría de los algoritmos generalmente solo están interesados en algunas funciones específicas: cosas como la función constante, la función lineal, la función logarítmica, la función exponencial, etc.
Un límite superior es una función que se encuentra encima de otra función. Un límite inferior es una función que se encuentra debajo de la otra función. Cuando hablamos de Big O y Big Omega, no nos importa si los límites están SIEMPRE por encima o por debajo de la otra función, solo que después de cierto punto siempre lo están (porque a veces los algoritmos se vuelven extraños para tamaños de entrada pequeños).
Hay un número infinito de límites superiores posibles para cualquier función dada, y un número infinito de límites inferiores posibles para cualquier función dada. Pero este es uno de esos momentos raros en los que hablamos de diferentes tamaños de infinitos. Para ser un límite superior, la función no debe estar por debajo de la otra función, por lo que descartamos el número infinito de funciones debajo de la otra función (por lo que es más pequeño que el conjunto de todas las funciones posibles).
Por supuesto, el hecho de que haya límites superiores infinitos no significa que todos sean útiles. La función f (∞) es un límite superior para cada función, pero eso es como decir “Tengo menos de una cantidad infinita de dólares”, lo que no es particularmente útil para determinar si no tengo un centavo o soy millonario. Por lo tanto, a menudo nos interesa un límite superior que sea “estrecho” (también conocido como “límite superior mínimo” o “superior”), para el cual no existe un límite superior mejor.
Mejor / peor caso + límite inferior / superior
Tenemos mejores / peores casos que representan las funciones superior e inferior de la función de tiempo de ejecución de un algoritmo. Tenemos límites superior e inferior que representan otras funciones que podrían estar encima o debajo (respectivamente) de cualquier otra función. Se pueden combinar para articular ideas clave sobre algoritmos.
En el peor de los casos, límite inferior: Una función que es un límite por debajo de la función de tiempo de ejecución de los algoritmos, cuando ese algoritmo recibe las entradas que maximizan el tiempo de ejecución del algoritmo.
En el peor de los casos, límite superior: Una función que es un límite por encima de la función de tiempo de ejecución de los algoritmos, cuando ese algoritmo recibe las entradas que maximizan el tiempo de ejecución del algoritmo.
Mejor caso límite inferior: Una función que es un límite por debajo de la función de tiempo de ejecución de los algoritmos, cuando ese algoritmo recibe las entradas que minimizan el tiempo de ejecución del algoritmo.
Mejor límite superior del caso: Una función que es un límite por encima de la función de tiempo de ejecución de los algoritmos, cuando ese algoritmo recibe las entradas que minimizan el tiempo de ejecución del algoritmo.
Ejemplos de límites de casos
Demos ejemplos concretos de cuándo podría interesarnos cada uno de estos:
En el peor de los casos, límite inferior: El ejemplo clásico aquí es la clasificación basada en la comparación, que se sabe que es Ω (n log (n)) en el peor de los casos. Independientemente del algoritmo que diseñe, puedo elegir un conjunto de entradas en el peor de los casos en las que la función de límite inferior más ajustada es log-lineal. No puede hacer un algoritmo que supere ese límite para el peor de los casos, y no debería molestarse en intentarlo. Es el sótano de la clasificación. Por supuesto, hay muchos límites inferiores para el peor de los casos: constante, lineal y sublineal son todos límites inferiores. Pero no son límites inferiores útiles, porque allí el límite inferior log-lineal es el más estrecho.
Mejor caso límite inferior: Insertion Sort funciona recorriendo la lista e insertando cualquier desorden que encuentre en el lugar correcto. Si la lista está ordenada, solo tendrá que recorrer la lista una vez sin hacer ninguna inserción. Esto significa que el límite inferior más ajustado del mejor caso es Ω (n). No puede hacerlo mejor que eso sin sacrificar la corrección, porque aún necesita poder recorrer la lista (tiempo lineal). Sin embargo, el límite inferior para el mejor de los casos es mejor que el límite inferior para el peor de los casos.
En el peor de los casos, límite superior: A menudo nos interesa encontrar un límite superior ajustado en el peor de los casos, porque entonces sabemos qué tan mal puede funcionar nuestro algoritmo en el peor de los casos. El peor de los casos de ordenación por inserción es una lista que está completamente fuera de orden (es decir, completamente invertida de su orden correcto). Cada vez que vemos un elemento nuevo, tenemos que moverlo al inicio de la lista, empujando todos los elementos posteriores hacia adelante (que es una operación de tiempo lineal, y hacerlo un número lineal de veces conduce a un comportamiento cuadrático). Sin embargo, todavía sabemos que este comportamiento de inserción será O (n2) en el peor de los casos, actuando como un límite superior ajustado para el peor de los casos. No es genial, pero es mejor que un límite superior de, digamos, exponencial o factorial. Por supuesto, esos son límites superiores válidos para el peor de los casos, pero nuevamente eso no es tan útil como saber que la cuadrática es un límite superior ajustado.
Mejor límite superior del caso: ¿Qué es lo peor que puede hacer nuestro algoritmo en el mejor de los casos? En el ejemplo anterior de encontrar un elemento en una lista, donde el primer elemento era nuestro elemento deseado, el límite superior es O (1). En el peor de los casos fue lineal, pero en el mejor de los casos, lo peor que puede pasar es que siga siendo constante. Esta idea en particular no suele ser tan importante como el límite superior del peor de los casos, en mi opinión, porque generalmente nos preocupa más tratar con el peor de los casos, no con el mejor de los casos.
Algunos de estos ejemplos son en realidad Ө, no solo O y Ω. En otros casos, podría haber elegido funciones de límite inferior o superior que no eran estrictas, pero que aún eran lo suficientemente aproximadas para ser útiles (recuerde, si no estamos siendo estrictos, ¡tengo un pozo infinito de donde sacar!). Tenga en cuenta que puede ser difícil encontrar ejemplos convincentes de diferentes combinaciones de caso / límite, porque las combinaciones tienen una utilidad diferente.
Conceptos erróneos y terminología
Con frecuencia, verá personas con conceptos erróneos sobre estas definiciones. De hecho, muchos Científicos de la Computación perfectamente buenos usarán estos términos de manera vaga e intercambiable. Sin embargo, la idea de casos y límites es distinta, y haría bien en asegurarse de comprenderlos. ¿Significa esto que surgirá la diferencia en tu día a día? No. Pero cuando elige entre unos pocos algoritmos diferentes, desea leer la letra pequeña sobre los casos y los límites. Alguien que le diga que su algoritmo tiene un límite superior de O (1) en el mejor caso probablemente esté tratando de engañarlo; asegúrese de preguntarle cuál es el límite superior del peor caso.
Permítanme ilustrar esto con un ejemplo:
El tiempo de ejecución en el peor de los casos para la ordenación rápida es Theta(n^2). Entonces, un límite inferior válido sería Omega(n) y un límite superior sería O(n^3). Esto dice que en el peor de los casos, la ordenación rápida tomará por lo menos tiempo lineal y a lo sumo tiempo cúbico.
Ahora bien, esa no es una declaración muy precisa, pero para algoritmos más complejos, tales declaraciones son lo mejor que podemos hacer.