Hay mucho de eso. El que mencionó es un enfoque basado en un árbol de decisión donde dice que la complejidad del árbol de decisión del algoritmo de clasificación es [math] \ Omega (n log n) [/ math], lo que significa lo siguiente.
Mire todos los árboles de decisión a los que puede dar lugar el algoritmo. Elija el que tenga la profundidad más corta. Luego demuestre que este árbol tiene profundidad al menos [matemática] \ Omega (n log n) [/ matemática] y de ahí la prueba.
Esto funciona para el algoritmo determinista. Para el caso del algoritmo aleatorio, la situación se vuelve un poco complicada. Trataré de explicar eso, pero antes de analizarlo, veamos cuáles son los puntos importantes a considerar.
- ¿Qué es la matemática profanada y dónde se usa?
- ¿Puedo convertirme en un buen científico de datos con programación pero no con habilidades matemáticas?
- ¿Puede un niño menor de 14 años que es malo en matemáticas aprender a programar juegos?
- ¿Por qué puedo codificar pero no puedo entender las matemáticas discretas?
- ¿Cómo se usa la teoría de juegos en la IA?
Lo primero a tener en cuenta al probar un límite inferior para un problema en particular es que cuáles son las instancias difíciles de este problema, es decir, cuáles son las entradas que son perjudiciales para cualquier algoritmo que intente resolver este problema. Luego, el siguiente paso es caracterizar este conjunto de entradas y tratar de argumentar que no importa qué algoritmo elijamos, el algoritmo será bastante malo en estas entradas.
Ahora, teniendo en cuenta esta idea, veamos algunas de las técnicas que prevalecen en la informática teórica. No voy a dar más detalles sobre ellos, pero una simple búsqueda en Google servirá.
Puede reducir un problema de complejidad de comunicación determinista al problema que le interesa. Existen ciertas técnicas en la complejidad de la comunicación, como el límite inferior de rango, el argumento de conjunto engañoso, el límite superior del tamaño del rectángulo monocromático que será útil en ese momento. (Estos términos, si no está familiarizado, necesitan un poco de búsqueda en Google).
Puede enmarcar su problema a una clase de circuito booleano (esta es una configuración no uniforme y, por lo tanto, un poco complicada) y usar los límites inferiores del circuito existente para hacer su trabajo.
Puede usar los límites inferiores de codificación de la rica literatura de la teoría de codificación.
Puede utilizar cualquier técnica de límite inferior utilizando álgebra lineal, como rigidez de rango de matriz, solidez de rango, etc., que se adapte a su trabajo. (Por lo general, esto funciona para algoritmos aleatorios).
Puede llegar a dos distribuciones en instancias SÍ y NO y vincular la distancia estadística entre ellas. (Nuevamente, funciona bien con algoritmos aleatorios).
Puedes usar la dirección dura del principio minimax de Yao. Primero muestra que para todas las distribuciones en las entradas, los algoritmos deterministas (con error) tienen un límite inferior en el tiempo de ejecución. Esto implicará un límite inferior aleatorio.
O puede usar el viejo y simple principio de los casilleros si eso funciona.
