Saltar al contenido principal

Cotas Inferiores

La complejidad de un problema es el costo del mejor algoritmo que resuelve ese problema. Por lo tanto, cada nuevo algoritmo que se encuentra para resolver ese problema establece una nueva cota superior a su complejidad. Por ejemplo, si descubrimos el ordenamiento por inserción, que toma tiempo O(n2)O(n^2), podemos decir que la complejidad del problema de ordenar es O(n2)O(n^2). Luego descubrimos MergeSort, y eso nos permite decir que la complejidad del problema de ordenar es en realidad menor, O(nlog⁡n)O(n\log n).

¿Cómo podemos determinar que hemos encontrado el algoritmo óptimo (el de menor costo posible) para resolver un problema? Debemos ser capaces de conocer su complejidad, pero mediante encontrar algoritmos sólo podremos establecer cotas superiores. Necesitamos entonces mecanismos para establecer cotas inferiores a un problema, es decir, demostrar que cualquier algoritmo que resuelva ese problema debe al menos pagar un determinado costo.

Por ejemplo, podemos convencernos de que para ordenar, el algoritmo debe al menos examinar todos los elementos del arreglo, para lo cual necesita realizar nn accesos. Eso significa que ningún algoritmo de ordenamiento puede tener costo o(n)o(n). Eso lo expresamos diciendo que una cota inferior para el problema de ordenar es Ω(n)\Omega(n). Note que esta cota inferior es válida, pero podría no ser (de hecho, no es), la mejor posible (la más alta posible). Decimos que esta cota puede no ser ajustada.

Para algunos problemas, se conocen cotas superiores de O(T(n))O(T(n)) y a la vez cotas inferiores de Ω(T(n))\Omega(T(n)). En ese caso, sabemos que

  • Los algoritmos que toman tiempo O(T(n))O(T(n)) son óptimos, es decir, no pueden existir algoritmos de complejidad inferior que resuelvan el problema.
  • La cota inferior de Ω(T(n))\Omega(T(n)) es ajustada, es decir, no puede haber una mejor cota inferior para el problema.
  • Conocemos la complejidad exacta del problema, que expresamos diciendo que el problema tiene complejidad Θ(T(n))\Theta(T(n)).

Para los problemas en que esto no ocurre, tenemos una cota superior (es decir, la complejidad de un algoritmo que lo resuelve) de O(T1(n))O(T_1(n)) y una cota inferior de Ω(T2(n))\Omega(T_2(n)), con T2(n)=o(T1(n))T_2(n) = o(T_1(n)). No sabemos si el algoritmo es óptimo, ni si la cota inferior es ajustada, y no conocemos la complejidad exacta del problema.

Se puede hablar de estas complejidades entendiendo que nos referimos al peor caso de un algoritmo que resuelva el problema, que es lo más común, pero también interesa conocer la complejidad de caso promedio de un problema, dada una cierta distribución de los inputs posibles. En el caso de algoritmos aleatorizados, podemos hablar de la complejidad esperada de un problema, que considera el peor input posible pero promedia sobre las elecciones aleatorias que hace el algoritmo. En este capítulo, sin embargo, sólo consideraremos algoritmos determinísticos (no aleatorizados).

Asimismo, nos puede interesar la complejidad no en términos asintóticos, sino en términos del costo exacto de los algoritmos (cantidad exacta de comparaciones que hace, o de accesos a un arreglo, etc.).

Note que una cota inferior puede centrarse en contar sólo cierto tipo de operaciones e ignorar otras, y aún así será válida como cota inferior.

En este capítulo veremos tres técnicas básicas para establecer cotas inferiores: la estrategia del adversario, reducciones, y teoría de la información.