Teoría de la Información
La Teoría de la Información es una disciplina que estudia la cantidad mínima de bits necesaria para representar un mensaje u objeto. Es decir, establece cotas inferiores para la cantidad de bits que debe emitir cualquier programa que represente un objeto, por comprimida que sea esta representación.
Es posible entonces obtener cotas inferiores a la cantidad de comparaciones que realiza un algoritmo sobre un input, si a partir de esas comparaciones podemos reconstruir ese input. En ese caso, el algoritmo podría considerarse potencialmente como un mecanismo de compresión, y la cantidad mínima de bits que debe emitir cualquier compresor se convierte en la cantidad mínima de comparaciones que debe realizar cualquier algoritmo. Debe notarse que este tipo de cotas aplica casi exclusivamente a algoritmos que deban proceder por comparaciones, pero a cambio puede establecer cotas tanto de peor caso como de caso promedio.
📄️ Cotas de peor caso
Para cotas de peor caso, la cota inferior es simplemente el logaritmo (base 2)
📄️ Búsqueda en un arreglo ordenado
Una alternativa al método del adversario usado en la búsqueda en un arreglo
📄️ Ordenar un arreglo
Consideremos el problema de ordenar $A[1,n]$. Ordenar implica aplicar una
📄️ Unir dos listas ordenadas
¿Cuántas comparaciones se necesitan para unir dos listas ordenadas, de
📄️ Cotas de caso promedio
El Teorema de Shannon establece que, si los elementos de $U = \{ u_1, \ldots,
📄️ Árboles de búsqueda óptimos
Nuestro problema se puede describir como: encontrar un árbol de búsqueda para