límite superior, límite inferior

Question

¿Qué significa probar un límite superior o un límite inferior a un algoritmo?

Answer 1

Probar un límite superior significa que ha demostrado que el algoritmo usará no más de algún límite en un recurso.

Probar un límite inferior significa que ha demostrado que el algoritmo usará no menos de algún límite en un recurso.

" Recurso " en este contexto podría ser tiempo, memoria, ancho de banda u otra cosa.

Answer 2

Los límites superior e inferior tienen que ver con la mínima y máxima "complejidad" de un algoritmo (uso esa palabra de manera aconsejable ya que tiene un significado muy específico en el análisis de complejidad).

Tome, por ejemplo, nuestro viejo amigo, el tipo burbuja. En un caso ideal en el que todos los datos ya están ordenados, el tiempo necesario es f (n), una función que depende de n , el número de elementos en la lista. Esto se debe a que solo tiene que hacer una pasada del conjunto de datos (con cero intercambios) para asegurarse de que su lista esté ordenada.

En un caso particularmente malo en el que los datos se ordenan en el orden opuesto al que desea, el tiempo necesario se convierte en f (n ² ). Esto se debe a que cada pase mueve un elemento a la posición correcta y necesita n pases para hacer todos los elementos.

En ese caso, los límites superior e inferior son diferentes, a pesar de que la complejidad big-O sigue siendo la misma.

Como comentario aparte, el tipo de burbuja está muy difamado (generalmente por buenas razones) pero puede tener sentido en ciertas circunstancias. De hecho, lo uso en una aplicación donde la mayor parte de los datos ya están ordenados y solo uno o dos elementos tienden a agregarse al final de la lista. Para agregar un elemento, y con una clasificación de burbuja de dirección inversa, puede garantizar que la nueva lista se ordenará en una sola pasada. Eso ilustra el concepto de límite inferior.

De hecho, podría hacer una optimización del tipo de burbuja que establece el límite inferior en f (1), simplemente proporcionando un dato adicional que indique si la lista está ordenada. Debería configurar esto después de ordenar y borrarlo al agregar un elemento al final.

Answer 3

Cualquiera que sea el límite (superior o inferior), siempre estamos hablando de la entrada en el peor de los casos que podemos considerar. Por ejemplo, al ordenar, asumimos que el peor de los casos es una lista de entrada sin clasificar.

Entiendo que los problemas tienen un límite inferior. Por ejemplo, decimos que el límite inferior de la clasificación basada en la comparación es \ Omega (n log n); no estamos asumiendo qué algoritmo particular de clasificación basado en comparación utilizamos. Cualquiera sea el algoritmo (combinación de clasificación, clasificación rápida, etc.), no podemos hacerlo mejor que este límite de \ Omega (n log n). Los límites inferiores nos dicen, intuitivamente, cuán difícil es un problema particular.

Cuando hablamos de un algoritmo específico , hablamos de límites superiores. Por ejemplo, decimos que el límite superior de la clasificación de burbujas es O (n ^ 2) y el límite superior de la clasificación de fusión es O (n log n). Los límites superiores, intuitivamente, nos dicen cuán bueno es un algoritmo particular para resolver el problema.