2011-02-15 36 views
5

He ideado varias estrategias, pero no estoy del todo seguro de cómo afectan el comportamiento general. Sé que el caso promedio es O (NlogN), así que supongo que estaría en la respuesta en alguna parte. Solo quiero poner NlogN + 1 si solo selecciono el primer ítem en el arreglo como el pivote para el quicksort, pero no sé si eso es correcto o no aceptable. Si alguien pudiera iluminarme sobre este tema, sería genial. ¡Gracias!Quicksort: ¿cómo las estrategias de elección de pivote afectan el comportamiento general de Big-oh de la oferta rápida?

estrategias posibles:

a) Matriz es al azar: escoger el primer punto, ya que es la opción más rentable.

b) La matriz está ordenada en su mayoría: elige el elemento del medio, por lo que es probable que complementemos la recursión binaria de la división a la mitad cada vez.

c) La matriz es relativamente grande: elija los índices primero, medio y último en el conjunto y compárelos, seleccionando el más pequeño para evitar el peor de los casos.

d) Realice 'c' con índices generados aleatoriamente para hacer que la selección sea menos determinista.

+0

No entiendo la pregunta. –

+0

P: Para las posibles estrategias que he elegido (a-d) ¿cómo afectarán el comportamiento general del algoritmo de la solución rápida? –

Respuesta

5

Un hecho importante que debe saber es que en una matriz de elementos distintos, el quicksort con una elección aleatoria de partición se ejecutará en O (n lg n). Hay muchas buenas pruebas de esto, y the one on Wikipedia en realidad tiene una discusión bastante buena de esto. Si está dispuesto a buscar una prueba un poco menos formal que sea matemáticamente sólida, la intuición es la siguiente. Cada vez que elijamos un pivote, digamos que un pivote "bueno" es un pivote que nos da al menos una división de 75%/25%; es decir, es mayor que al menos el 25% de los elementos y, como máximo, el 75% de los elementos. Queremos consolidar el número de veces que podemos obtener un pivote de este tipo antes de que termine el algoritmo. Supongamos que obtenemos k divisiones de este tipo y consideramos el tamaño del subproblema más grande generado de esta manera. Tiene un tamaño como máximo (3/4) k n, ya que en cada iteración nos estamos deshaciendo de al menos un cuarto de los elementos. Si consideramos el caso específico donde k = log 3/4 (1/n) = log 4/3 n, entonces el tamaño del subproblema más grande después de que se elijan k buenos pivotes será 1, y la recursión detener. Esto significa que si elegimos obtener O (lg n) buenos pivotes, la recursión terminará. Pero en cada iteración, ¿cuál es la posibilidad de obtener ese pivote? Bueno, si elegimos el pivote al azar, entonces hay un 50% de probabilidad de que esté en el medio 50% de los elementos, y así sucesivamente, elegiremos dos pivotes aleatorios antes de obtener un buen pivote. Cada paso de elegir un pivote toma O (n) tiempo, por lo que debemos pasar aproximadamente O (n) tiempo antes de obtener cada pivote. Como obtenemos como máximo O (lg n) buenos pivotes, el tiempo de ejecución general es O (n lg n) según las expectativas.

Un detalle importante en la discusión anterior es que si reemplaza la división del 75% con una división constante, es decir, una división de (100% k/k%), el análisis asintótico es el mismo. Obtendrá que la quicksort tome, en promedio, O (n lg n) tiempo.

La razón por la que mencioné esta prueba es porque te da un buen marco para pensar cómo elegir un pivote en la oferta rápida. Si puede elegir un pivote que esté bastante cerca del centro en cada iteración, puede garantizar el tiempo de ejecución O (n lg n).Si no puede garantizar que obtendrá un buen pivote en cualquier iteración, pero puede decir que con la expectativa solo requiere un número constante de iteraciones antes de obtener un buen pivote, entonces también puede garantizar O (n lg n) tiempo de ejecución esperado

Dado esto, echemos un vistazo a sus esquemas de pivote propuestos. Para (a), si la matriz es aleatoria, elegir el primer elemento como pivote es esencialmente lo mismo que elegir un pivote aleatorio en cada paso, y así, mediante el análisis anterior, obtendrás O (n lg n) en tiempo de ejecución con expectativas . Para (b), si sabes que la matriz está ordenada en su mayoría, elegir la mediana es una buena estrategia. La razón es que si podemos decir que cada elemento está "bastante cerca" de donde debería estar en la secuencia ordenada, entonces puedes argumentar que cada pivote que elijas es un buen pivote, dándote la O (n lg n) tiempo de ejecución que desee. (El término "bastante cerca" no es matemáticamente preciso, pero creo que podrías formalizar esto sin demasiada dificultad si quisieras).

En cuanto a (c) y (d), de los dos, (d) es el único garantizado para obtener O (n lg n) en la expectativa. Si determinísticamente eliges ciertos elementos para utilizarlos como pivotes, tu algoritmo será vulnerable a las secuencias determinísticas que pueden degenerarlo en el comportamiento O (n). De hecho, McIlroy cuenta con un documento realmente interesante llamado "A Killer Adversary for Quicksort" que describe cómo puede tomar cualquier ruta de acceso determinista y construir la peor entrada de un caso patológico mediante una función de comparación maliciosa. Es casi seguro que desea evitar esto en cualquier implementación de quicksort real, ya que de lo contrario los usuarios maliciosos podrían lanzar ataques DoS contra su código alimentando estas secuencias asesinas para forzar a su programa a ordenar en tiempo cuadrático y así colgar. Por otro lado, debido a que (d) está escogiendo sus puntos de muestra aleatoriamente, no es vulnerable a este ataque, porque en cualquier secuencia la elección de los pivotes es aleatoria.

Aunque, curiosamente, para (d), aunque no hace daño elegir tres elementos aleatorios y tomar la mediana, no es necesario que haga esto. La prueba anterior es suficiente para mostrar que obtendrá O (n lg n) en la expectativa con una única opción de pivote aleatorio. De hecho, no sé si elegir la mediana de tres valores aleatorios mejorará el rendimiento del algoritmo de la solución rápida, aunque dado que el quicksort es siempre Ω (n lg n) ciertamente no será mejor que seleccionar elementos aleatorios como el pivotes.

Espero que esto ayude un poco. Me encanta el algoritmo de solución rápida y todas las decisiones de diseño involucradas en la construcción de una buena implementación de quicksort. :-)

+0

Gracias fue extremadamente útil, espero que haya disfrutado escribiendo esto?:) –

+0

¡Ah, y todo el ataque de DoS fue realmente interesante! Es sorprendente lo que los piratas informáticos pueden hacer con una simple información. –

+0

@ Mr_CryptoPrime- Esto fue muy divertido de escribir; gracias por hacer una pregunta tan genial! Y me alegra que hayas disfrutado el enlace; lo clasifico entre mis trabajos favoritos de CS. – templatetypedef

-1

El mejor pivote es aquel que puede dividir la matriz exactamente en dos mitades. La mediana de la matriz es, por supuesto, la mejor opción. Voy a sugerir este enfoque: -
select some random indexes
calculate median of these elements
Use this as pivot element

Desde el algoritmo de búsqueda de O (n) la mediana, creo que 5 índices de azar deberían ser suficiente.

+1

-1 Esta afirmación parece no respaldada. El algoritmo de búsqueda de la mediana de O (n) elige dividir la secuencia en bloques de cinco elementos basándose en un análisis matemático muy cuidadoso del rendimiento del algoritmo. Puede tener razón en que elegir la mediana de cinco elementos aleatorios es bueno, pero necesita respaldar este reclamo. Además, si solo vas a elegir la mediana de elementos aleatorios, ¿por qué no elegir un pivote aleatorio? Se puede demostrar que esto le proporciona O (n lg n) el comportamiento esperado con alta probabilidad. – templatetypedef

0

Tiene que comprender que ya hay muchos algoritmos que le permitirán mantener una O (nlog (n)) complejidad. El uso de randomized quick sort ha esperado una complejidad temporal de O (nlog (n)), y generalmente se considera mejor que otros enfoques.

Sería capaz de mantener O (nlog (n)) si tuviera una combinación de todas las anteriores, es decir, aplicar condicionalmente una de ellas en función del "perfil" de su conjunto de datos de entrada. Dicho esto, categorizar un conjunto de datos de entrada en sí mismo es un desafío. En cualquier caso, para hacerlo mejor, debe investigar en su conjunto de datos de entrada y elegir las alternativas posibles.

Cuestiones relacionadas