Hablemos de algoritmos. Los novatos a menudo los perciben como algo difícil, complejo e incomprensible, y esto es parcialmente cierto, pero los algoritmos son la base. Y cuanto mejor conozca los conceptos básicos de su especialidad, más probabilidades tendrá de sobresalir en ella.
Hoy veremos un hermoso problema de algoritmos. No vamos a asustar a las personas para que no trabajen con algoritmos desde el principio, por lo que en nuestro análisis no habrá árboles de segmentos en expansión, optimizaciones variadas del problema de la mochila o pruebas probabilísticas de simplicidad. Algos fáciles de usar.
Aquí está el desafío: encuentre la máxima diferencia entre vecinos.
Se da una matriz de N números enteros. No está ordenado de ninguna manera y los números se pueden repetir. Digamos que lo ordenamos y calculamos la diferencia entre cada par de elementos consecutivos. Es necesario encontrar la máxima diferencia de este tipo y hacerlo de la manera más óptima.
¿Complicado? Puede intentar hacer esto antes de hacer clic en "Leer más" y luego comprobar la solución.
Entonces vamos. Máxima diferencia entre vecinos.
Considere un ejemplo:
Sea una matriz de N = 11 elementos.
Primero, solucionemos el problema ingenuamente, a menudo ayuda. Podemos hacer exactamente lo que el problema requiere que hagamos: ordenar los números y encontrar la diferencia entre elementos adyacentes. La complejidad de la solución variará según la clasificación que utilicemos.
Si usamos qsort o mergesort , entonces la complejidad del tiempo es ... Si sabemos que los números están distribuidos de forma bastante densa en el conjunto de números enteros, entonces podemos usar la ordenación por conteo. Entonces tenemos , donde U es la diferencia entre el elemento máximo y mínimo. El caso es relativamente raro, pero vale la pena recordar esta posibilidad.
Después de ordenar, obtenemos una matriz:
Escribamos una serie de diferencias:
Obtenemos que la diferencia máxima es 6.
Ahora pensemos, ¿es posible resolver el problema más rápido? Al iterar sobre pares de elementos vecinos, consideraremos muchos pares con una pequeña diferencia. Es posible que estos pares nunca den la mayor diferencia. De hecho, en la matriz ordenada tenemos un par de números adyacentes, sea la diferencia entre el máximo y el mínimo ... Entonces la mayor diferencia debería tener al menos ... Esta estimación es cierta según el principio de Dirichlet.
Si las palomas se colocan en jaulas y el número de palomas es mayor que el número de jaulas, entonces al menos una de las jaulas contiene más de una paloma.
9 células contienen 10 palomas, de acuerdo con el principio de Dirichlet, al menos una célula contiene más de una paloma ( Wikipedia )
Let ... , - i-ésimo elemento de la matriz ordenada. Entonces ...
Si asumimos que el máximo de todo D [i] es menor , luego la cantidad total será estrictamente menor que U, una contradicción.
Genial, ¡obtuvimos un límite inferior para la diferencia máxima! Ahora intentemos localizar de alguna manera los elementos que están demasiado cerca unos de otros: dividimos el segmento del elemento mínimo al máximo en medios intervalos de longitud ... Cada elemento caerá exactamente en un medio intervalo. Obtendremos una partición de todos los elementos en grupos disjuntos, también se les llama lotes.
Es muy simple determinar en cuál de ellos cayó el elemento x: necesita calcular 1 + int ((x - a_min) / L) (numeramos desde uno), donde a_min es el elemento mínimo en la matriz A, se puede encontrar en una pasada la matriz original. La única excepción será el elemento máximo: es mejor crear elementos con ese valor en un lote separado.
La figura muestra la distribución del ejemplo descrito anteriormente. Para mayor claridad, hagamos esto con nuestras manos:
La distribución de lotes se realiza en tiempo lineal y requiere memoria adicional. Tenga en cuenta que los artículos de un lote no pueden dar la diferencia máxima entre dos artículos. Hemos seleccionado especialmente su tamaño de esta manera.
¿Dónde puede haber dos elementos adyacentes? ¡Por supuesto, en lotes vecinos no vacíos! Por ejemplo, en la figura, los elementos del tercer y sexto lote pueden ir en una fila en una matriz ordenada, ya que los lotes entre ellos están vacíos. Está claro que solo dos elementos serán adyacentes: el máximo del tercer lote y el mínimo del sexto. Del mismo modo, los candidatos a un par con la máxima diferencia serán el elemento máximo del primer lote y el elemento mínimo del tercero.
Anotemos todos los posibles pares de elementos que pueden dar la mayor diferencia. Denotemos como min (i) - el elemento mínimo en el i-ésimo grupo, como max (i) - el elemento máximo.
max (1) = -1 min (3) = 3
max (3) = 4 min (6) = 10
max (6) = 10 min (8) = 15
max (8) = 15 min (10) = 20
max (10) = 21 min (11) = 22
Hemos identificado pares que vale la pena considerar. En la práctica, es necesario hacer una pasada por todos los lotes, mantener el último lote no vacío y el valor máximo en él. Cuando nos encontremos con el siguiente lote no vacío, encontraremos el mínimo e intentaremos actualizar la respuesta.
Estaremos encantados, solucionamos el problema a tiempo. ...
De hecho, utilizamos una idea bastante conocida y, de hecho, dimos los primeros pasos de la clasificación de bolsillo, en el original se llama clasificación de cubo .
Los artículos se organizan en cestas y luego los artículos de cada cesta se ordenan
En el peor de los casos, funciona para , pero el tiempo de ejecución medio con un número suficiente de lotes y una distribución uniforme de elementos es ...
"Pero espera, pero ¿qué pasa con el caso cuando , ¿por qué no lo has considerado? ”- preguntará el lector atento. Este caso está degenerado, por lo que no lo hemos considerado, pero hagámoslo ahora para completarlo.
Si la diferencia entre el mínimo y el máximo es cero, entonces la diferencia máxima también es cero. De hecho, eso es todo.