En ciencias de la computación , el método de diferenciación más grande es un algoritmo para resolver el problema de la partición y la partición de números de varias vías . También se llama algoritmo Karmarkar-Karp en honor a sus inventores, Narendra Karmarkar y Richard M. Karp . [1] A menudo se abrevia como LDM. [2] [3]
La entrada al algoritmo es un conjunto S de números y un parámetro k . La salida requerida es una partición de S en k subconjuntos, de modo que las sumas en los subconjuntos sean lo más iguales posible. Los pasos principales del algoritmo son:
Por ejemplo, si S = {8,7,6,5,4}, los conjuntos de diferencias resultantes son 6,5,4,1, luego 4,1,1, luego 3,1 y luego 2.
El paso 3 construye los subconjuntos en la partición retrocediendo. El último paso corresponde a {2},{}. Entonces 2 se reemplaza por 3 en un conjunto y 1 en el otro conjunto: {3},{1}, luego {4},{1,1}, luego {4,5}, {1,6}, luego { 4,7,5}, {8,6}, donde la suma-diferencia es de hecho 2.
La complejidad del tiempo de ejecución de este algoritmo está dominada por el paso 1 (clasificación), que toma O ( n log n ).
Tenga en cuenta que esta partición no es óptima: en la partición {8,7}, {6,5,4} la diferencia de suma es 0. Sin embargo, hay evidencia de que proporciona una partición "buena":