Me habéis preguntado en clase si se conoce algún algoritmo mejor que el de coste cuadrático visto en clase para el problema de la transparencia 84 de algoritmos voraces.

He encontrado una respuesta en el libro Computer Algorithms, de Ellis Horowitz, Sartaj Sahni, and Sanguthevar Rajasekaran (Computer Science Press, 1998):

It can be reduced from O(n²) to nearly O(n) by using the disjoint set union and find algorithms…

Se refiere a los algoritmos para implementar conjuntos disjuntos o clases de equivalencia (union-find) que vimos en clase hace unos días (descritos en la página de material adicional). El coste de la solución propuesta es O(n α(2n,n)), donde α(2n,n) es la inversa de la función de Ackermann (y crece muy, muy despacio, siendo prácticamente imposible encontrar un n para el que la función α valga más de 4), por lo que el coste de la solución resulta, prácticamente, lineal.

Os dejo en la página de material adicional esta sección del libro de Horowitz et al. en la que se describe el problema y algo sobre esa solución (no es fácil de leer).