Aquí hay un ejemplo no completamente trivial en el que puedo pensar: cualquier algoritmo determinista A que pueda encontrar la mediana de una matriz en O (n) puede usarse para encontrar el k-ésimo elemento más grande, para cualquier k, en O (n ): simplemente ejecute QuickSelect y use A para encontrar el pivote en cada paso. La prueba de que este nuevo algoritmo se ejecuta en O (n) utiliza el caso 3 del teorema maestro.
Dicho esto, hay una buena razón por la que no ves muchos de estos algoritmos en la práctica. El caso 3 del teorema maestro es el caso en el que casi todo el trabajo se realiza en el caso base, fuera de todas las llamadas recursivas. Y como el tiempo de ejecución de la parte recursiva es pequeño, generalmente hay una solución no recursiva que es más simple y tiene la misma complejidad de tiempo asintótica. (Intuitivamente, la segunda solución solo hace todo el trabajo en el caso base, en lugar de hacer casi todo el trabajo).
- Dada una matriz S de n enteros, ¿hay elementos a, b, c en S tales que a + b + c = 0? ¿Encuentra todos los tripletes únicos en la matriz que da la suma de cero?
- ¿Cuál es el mejor algoritmo de aprendizaje automático sin supervisión para la segmentación de imágenes basada en color?
- ¿Cuáles son los mejores libros para aprender el comercio algorítmico con Python?
- ¿Es difícil seguir 100 días de algoritmos?
- Supongamos que eliminamos un borde de un árbol de expansión y luego agregamos un borde diferente para que permanezca conectado. ¿Seguirá siendo un árbol de expansión?
