Hola habrozhiteli! Este libro se basa en los cursos algorítmicos en línea que Tim Rafgarden dirige en Coursera y Stanford Lagunita, y estos cursos han surgido gracias a las conferencias que ha estado dando a los estudiantes de la Universidad de Stanford durante muchos años.
Los algoritmos son el corazón y el alma de la informática. No puede prescindir de ellos, están en todas partes, desde el enrutamiento de la red y los cálculos genómicos hasta la criptografía y el aprendizaje automático. El "Algoritmo perfecto" lo convertirá en un verdadero profesional que establecerá tareas y las resolverá magistralmente tanto en la vida como en una entrevista al contratar cualquier empresa de TI. Tim Rafgarden hablará sobre análisis asintótico, notación big-O, algoritmos de división y conquista, aleatorización, clasificación y selección. El libro está dirigido a aquellos que ya tienen experiencia en programación. Pasará a un nuevo nivel para ver el panorama general, para comprender los conceptos de bajo nivel y los matices matemáticos.
* 6.3. DSelect Algorithm
El algoritmo RSelect se ejecuta en tiempo lineal para cada entrada, en el que la expectativa matemática se asocia con elecciones aleatorias realizadas por el algoritmo. ¿Se requiere aleatorización para la selección lineal? En esta sección y más, este problema se resuelve utilizando un algoritmo lineal determinista para el problema de elección.
Para la tarea de clasificación, el tiempo de ejecución promedio del algoritmo QuickSort aleatorizado O (n log n) es el mismo que el algoritmo determinista MergeSort, y ambos algoritmos QuickSort y MergeSort son algoritmos útiles para uso práctico. Por otro lado, aunque el algoritmo de selección lineal determinista descrito en esta sección funciona bien en la práctica, no compite con el algoritmo RSelect. Esto sucede por dos razones: debido a los grandes factores constantes en el tiempo de funcionamiento del algoritmo DSelect y el trabajo realizado por el algoritmo asociado con la asignación y gestión de RAM adicional. Sin embargo, las ideas en el algoritmo son tan geniales que no puedo evitar contarte sobre ellas.
6.3.1. Idea brillante: mediana de medianas
El algoritmo RSelect es rápido, porque hay una alta probabilidad de que los elementos de soporte aleatorios sean bastante buenos, proporcionando una división aproximadamente equilibrada de la matriz de entrada después de la separación, además, elementos de soporte bastante buenos progresan rápidamente. Si no se nos permite usar la aleatorización, ¿cómo podemos calcular un elemento de referencia bastante bueno sin hacer demasiado trabajo?
La ingeniosa idea en una elección lineal determinista es utilizar la "mediana de las medianas" como un proxy de la verdadera mediana. El algoritmo considera elementos de la matriz de entrada como equipos deportivos y celebra un torneo eliminatorio en dos rondas, cuyo campeón es el elemento de apoyo; ver también fig. 6.1.
La primera ronda es una etapa grupal con elementos en las posiciones 1–5 de la matriz de entrada como el primer grupo, elementos en las posiciones 6–10 como el segundo grupo, y así sucesivamente. El ganador de la primera ronda de un grupo de cinco elementos se define como la mediana del elemento (es decir, el tercero más pequeño). Ya que hay
grupos de cinco elementos, hay
primeros ganadores (Como de costumbre, ignoramos las fracciones por simplicidad). Un campeón del torneo se define como la mediana de los ganadores de la primera ronda.
6.3.2. Pseudocódigo para el algoritmo DSelect
¿Cómo calcular realmente la mediana de las medianas? La implementación de la primera etapa del torneo de eliminación es simple, ya que cada cálculo de la mediana incluye solo cinco elementos. Por ejemplo, cada uno de estos cálculos se puede realizar por la fuerza bruta (para cada una de las cinco posibilidades, verifique en detalle si es un elemento intermedio) o utilice nuestra información sobre el problema de clasificación (sección 6.1.2). Para implementar la segunda etapa, calculamos la mediana de
ganadores de la primera ronda de forma recursiva.
Las líneas 1–2 y 6–13 son idénticas al algoritmo RSelect. Las líneas 3–5 son la única parte nueva del algoritmo; calculan la mediana de la mediana de la matriz de entrada, reemplazando la línea en el algoritmo RSelect, que selecciona el elemento de referencia al azar.
Las líneas 3 y 4 calculan a los ganadores de la primera ronda del torneo de eliminación, donde el elemento central de cada grupo de cinco elementos se calcula utilizando el método de fuerza bruta o el algoritmo de clasificación, y copia a estos ganadores al nuevo conjunto C. La línea 5 calcula al campeón del torneo calculando recursivamente la mediana del conjunto C; ya que C tiene una longitud (tentativamente)
-o estadísticas ordinales de la matriz C. No se utiliza aleatorización en ningún paso del algoritmo.
6.3.3. Comprender el algoritmo DSelect
Una llamada recursiva al algoritmo DSelect al calcular un elemento de referencia puede parecer peligrosamente cíclica. Para comprender lo que está sucediendo, primero designemos el número total de llamadas recursivas.
La respuesta correcta es: (c). Descartando el caso base y el caso feliz en el que el elemento de referencia son las estadísticas de pedido requeridas, el algoritmo DSelect realiza dos llamadas recursivas. Para entender por qué, no te excedas; simplemente verifique el pseudocódigo del algoritmo DSelect línea por línea. La línea 5 tiene una llamada recursiva y otra en la línea 11 o 13.
Hay dos preguntas comunes confusas sobre estas dos llamadas recursivas. Primero, ¿no es un hecho que el algoritmo RSelect hace solo una llamada recursiva, la razón por la cual funciona más rápido que nuestros algoritmos de clasificación? ¿DSelect no abandona esta mejora haciendo dos llamadas recursivas? La sección 6.4 muestra que, dado que la llamada recursiva adicional en la línea 5 debería resolver solo una subtarea relativamente pequeña (con el 20% de los elementos en la matriz original), aún podemos guardar el análisis lineal.
En segundo lugar, dos llamadas recursivas juegan roles fundamentalmente diferentes. El propósito de la llamada recursiva en la línea 5 es determinar un buen elemento de referencia para la llamada recursiva actual. El objetivo de la llamada recursiva en la línea 11 o 13 es el habitual: resolver recursivamente la tarea restante más pequeña que deja la llamada recursiva actual. Sin embargo, la estructura recursiva en el algoritmo DSelect sigue completamente la tradición de todos los demás algoritmos de divide y vencerás que estudiamos: cada llamada recursiva realiza un pequeño número de llamadas recursivas posteriores con subtareas estrictamente más finas y realiza un trabajo adicional. Si no nos preocupa que algoritmos como MergeSort o QuickSort se ejecuten para siempre, entonces no deberíamos preocuparnos por el algoritmo DSelect.
6.3.4. Tiempo de ejecución del algoritmo DSelect
El algoritmo DSelect no es solo un programa claramente articulado que se completa en una cantidad limitada de tiempo: se ejecuta en tiempo lineal, haciendo más trabajo solo en un factor constante de lo necesario para leer los datos de entrada.
Teorema 6.6 (tiempo de funcionamiento del algoritmo DSelect). Para cada matriz de entrada de longitud n ≥ 1, el tiempo de funcionamiento del algoritmo DSelect es O (n).
A diferencia del tiempo de ejecución del algoritmo RSelect, que en principio no puede ser mayor que Θ (n2), el tiempo de ejecución del algoritmo DSelect siempre es igual a O (n). Sin embargo, en la práctica, debe preferir RSelect al algoritmo DSelect, porque el primero funciona en el mismo lugar, y la constante oculta en el tiempo de operación promedio "O (n)" en el Teorema 6.1 es menor que la constante oculta en el Teorema 6.6.
»Se puede encontrar más información sobre el libro en
el sitio web del editor»
Contenidos»
ExtractoPara Khabrozhiteley 20% de descuento en el cupón -
AlgoritmosTras el pago de la versión en papel del libro, se envía una versión electrónica del libro por correo electrónico.
PD: el 7% del costo del libro se destinará a la traducción de nuevos libros de computadora, la lista de libros entregados a la imprenta está
aquí .