Desde un punto de vista puramente teórico, no, no hará la diferencia. Desde un punto de vista práctico en términos de creación de heurística para atacar problemas NP-duros, puede que en algunos casos, pero no hay garantías.
Primero, analicemos la perspectiva teórica: ¿podría un árbol rojo-negro ser una parte necesaria de una solución P = NP? La respuesta aquí es claramente ‘No’ (omitiendo la pregunta por el momento de si P = NP o no).
Un árbol rojo-negro es solo un medio para mantener un árbol binario ordenado equilibrado. Por lo tanto, es útil cuando quiero ver si tengo un artículo en particular en un conjunto ordenado, y deseo hacerlo rápidamente, o si quiero encontrar información sobre un artículo en un conjunto ordenado. Sin embargo, si quisiera hacer una búsqueda lineal a través de una lista sin ordenar, aún podría resolver cualquier problema, sería más lento.
- ¿Cuál es el enfoque algorítmico para invertir un árbol binario dado?
- ¿Qué es un algoritmo increíble que encontraste?
- ¿Se aplican las estructuras de datos y algoritmos para C / C ++ a JavaScript?
- Cómo resolver esta cuestión de las fuerzas
- ¿Cómo podemos hacer un programa para encontrar la suma y el promedio de los valores de la matriz? ¿Por favor ayuda?
¿Cuánto más lenta sería una búsqueda lineal? Bueno, para un árbol rojo-negro, la búsqueda de información requiere O (log n) pasos donde n es el número de elementos de la lista, y para una búsqueda lineal, por supuesto, toma O (n). Tenga en cuenta que la diferencia está en el tiempo de procesamiento todavía está limitado por polinomios.
Digamos, en aras del argumento de que alguien encontró un medio de resolver un problema NP-completo en el tiempo O (n ^ p) para alguna constante constante p, y donde n se relaciona con el tamaño del problema. Y supongamos por el momento que su método requiere el uso de un árbol rojo-negro. Ahora, reemplace cada uso del árbol rojo-negro con una referencia a una lista sin clasificar. Afirmo que la solución aún tendría un límite de tiempo polinómico. De hecho, el tiempo sería peor, O ((n ^ (p + 1)) / log (n)).
Cualquier técnica de optimización que produzca una aceleración ligada al polinomio no será esencial para encontrar una solución de tiempo polinomial a los problemas de NP completo. Un árbol rojo-negro proporciona solo una aceleración O (n / logn) en comparación con una lista no ordenada, que es un enlace polinómico. Por lo tanto, un árbol rojo-negro no puede ser esencialmente mejor que una lista sin clasificar para encontrar una solución de tiempo polinomial para problemas NP-completos.
Cuando se trata de ciertas heurísticas para quizás no resolver realmente un problema de NP completo en todos los casos, entonces un árbol rojo-negro podría ser útil para algunos enfoques. Aquí, sin embargo, depende completamente de la naturaleza del enfoque. No esperaría que fuera una respuesta universal.
