¿Cómo usar argumentos adversos para la selección y el tipo de inserción?

Me pidieron que encontrara los argumentos adversarios necesarios para encontrar los límites inferiores para la selección y el tipo de inserción. No pude encontrar una referencia en ningún lado.

Tengo algunas dudas al respecto. Entiendo que los argumentos adversos generalmente se usan para encontrar límites inferiores para ciertos "problemas" en lugar de "algoritmos".

Entiendo el problema de fusión. Pero, ¿cómo podría escribir uno para la selección y el tipo de inserción?

Según su comentario, parece que está confundiendo el significado de límites inferiores, límites superiores y notación asintótica. Por ejemplo, tome el orden de inserción. Su mejor tiempo de ejecución es (esto sucede cuando la entrada ya está ordenada). Su peor tiempo de ejecución es (esto sucede cuando la entrada está en orden inverso). Entonces, dado que el tiempo de ejecución cae entre una función lineal de y una función cuadrática de , puede decir que el tiempo de ejecución de Insertion Sort es tanto como . Es importante entender en este caso que no puede decir que el tiempo de ejecución es$\Theta(n)$$\Theta(n^2)$$n$$n$$\Omega(n)$$O(n^2)$$\Omega(n^2)$. ¿Por qué? Porque existe una entrada que hace que el algoritmo se ejecute en . Sin embargo, puede decir que el peor tiempo de ejecución es , nuevamente porque existe una entrada que hace que el algoritmo se ejecute en . Sin embargo, generalmente usamos la notación para el peor de los casos, ya que estamos interesados ​​en un límite superior en el número de operaciones realizadas por el algoritmo.$O(n)$$\Omega(n^2)$$\Omega(n^2)$$O$

Ahora, pensemos en un argumento adverso para el orden de inserción (puede intentar derivar uno para el orden de selección aplicando las mismas ideas).

Considere el algoritmo de inserción de clasificación jugando contra un oponente que llamaremos adversario. El objetivo del adversario es proporcionar una entrada X para el algoritmo que maximice el número de comparaciones realizadas por el algoritmo. Esto generalmente se analiza en el contexto de los árboles de decisión . Un árbol de decisión muestra todas las secuencias posibles de comparaciones que el algoritmo podría hacer. Cada nodo interior de un árbol de decisión representa una comparación única. Los dos hijos de un nodo representan los dos resultados de la comparación (sí / no o verdadero / falso). Cada hoja representa una salida posible. Para los algoritmos de clasificación, las hojas son permutaciones.de las llaves El algoritmo comienza en la raíz y sigue un camino hacia una hoja. En cada nodo interno, la respuesta para la comparación realizada le dice al algoritmo qué nodo debe visitarse a continuación. Cuando el algoritmo alcanza una hoja, genera su permutación correspondiente. El tiempo de ejecución de un algoritmo (visto como un árbol de decisión) para una entrada dada es el número de comparaciones realizadas en la ruta desde la raíz hasta la hoja de salida. Ahora, el adversario tiene una estrategia simple que funcionará contra cualquier algoritmo de ordenación basado en la comparación, incluida la inserción de clasificación: cada vez que el algoritmo hace una comparación, el adversario elige la respuesta que eliminará la menor cantidad posible de permutaciones.

En general, debido al hecho de que con elementos hayposibles permutaciones, cualquier árbol de decisión para ordenar debe tener al menoshojas, por lo que debe tener profundidad (por aproximación de Stirling). Para el orden de inserción, el adversario puede crear una entrada particular que haga que el árbol de decisión correspondiente tenga una profundidad de al menos .$n$$n!$$n!$$\Omega(\log(n!)) = \Omega(n\log n)$$\Omega(n^2)$

El algoritmo utiliza una matriz para almacenar los elementos de entrada y se basa en la siguiente invariante:$A[1 .. n]$

Al comienzo de cada iteración del bucle for, la submatriz consta de los elementos originalmente en , pero en orden ordenado.$A[1 .. j-1]$$A[1 .. j-1]$

Por lo tanto, en cada iteración, los elementos en ya están ordenados, y el algoritmo examina y lo inserta en su lugar final, comparando el valor de con el valor de los elementos en , comenzando desde y regresando a y así sucesivamente hasta que ya no sea el más grande en el comparación. Los elementos en están en un estado desconocido (con respecto al orden de clasificación) y se procesarán en iteraciones posteriores.$A[1 .. j-1]$$A[j]$$A[j]$$A[1 .. j-1]$$A[j-1]$$A[j-2]$$A[j]$$A[j+1 .. n]$

Aquí está la estrategia del adversario. Sabiendo que el algoritmo funciona insertando en su lugar apropiado moviendo los elementos en , entonces la estrategia obvia es maximizar en la iteración el número de elementos que deben ser movido para acomodar . Esto se logra fácilmente eligiendo cuidadosamente la entrada para que esté en orden inverso . De hecho, en este caso, el número de elementos que se deben mover en cada iteración es . Esto lleva al peor tiempo de ejecución (determinado por la serie aritmética correspondiente).$A[j]$$A[1 .. j-1]$$j$$A[j]$$j-1$$\Omega(n^2)$