algorithm - ordenamiento - Cómo calcular el orden(gran O) para algoritmos más complejos(por ejemplo, quicksort)

quicksort explicacion

Question

Sé que hay un montón de preguntas sobre la notación O grande, que ya he comprobado:

• Explicación inglesa simple de Big O
• Big O, ¿cómo lo calculas / aproximas?
• Big O Notation Tarea - ¿Análisis de algoritmo de fragmento de código?

para nombrar unos pocos.

Sé por "intuición" cómo calcularlo para n , n^2 , n! y así, sin embargo, estoy completamente perdido en cómo calcularlo para los algoritmos que son log n , n log n , n log log n y así.

Lo que quiero decir es que sé que la ordenación rápida es n log n (en promedio) .. pero, ¿por qué ? Lo mismo para fusionar / peinar, etc.

¿Podría alguien explicarme de una manera no demasiado matemática? ¿Cómo se calcula esto?

La razón principal es que estoy a punto de tener una gran entrevista y estoy bastante seguro de que pedirán este tipo de cosas. He investigado durante unos días ahora, y todos parecen tener una explicación de por qué el tipo de burbuja es n ^ 2 o la explicación ilegible (para mí) en Wikipedia

Answer 1

Al aplicar un algoritmo de dividir y conquistar en el que se divide el problema en subproblemas hasta que sea tan simple que sea trivial, si la partición sale bien, el tamaño de cada subproblema es n / 2 o aproximadamente. Este suele ser el origen del log(n) que surge en la complejidad de la gran O: O(log(n)) es el número de llamadas recursivas necesarias cuando la partición va bien.

Answer 2

Echa un vistazo al ejemplo de la "guía telefónica" que aparece aquí: ¿Qué es una explicación simple en inglés de la notación "O grande"?

Recuerde que Big-O tiene que ver con la escala : ¿cuánto más operará este algoritmo a medida que crezca el conjunto de datos?

O (log n) generalmente significa que puede cortar el conjunto de datos a la mitad con cada iteración (por ejemplo, búsqueda binaria)

O (n log n) significa que está realizando una operación O (log n) para cada elemento en su conjunto de datos

Estoy bastante seguro de que ''O (n log log n)'' no tiene ningún sentido. O si lo hace, se simplifica a O (n log n).

Answer 3

El logaritmo es la operación inversa de la exponenciación. Un ejemplo de exponenciación es cuando se duplica el número de elementos en cada paso. Por lo tanto, un algoritmo logarítmico a menudo reduce a la mitad el número de elementos en cada paso. Por ejemplo, la búsqueda binaria entra en esta categoría.

Muchos algoritmos requieren un número logarítmico de pasos grandes, pero cada paso grande requiere O (n) unidades de trabajo. Mergesort entra en esta categoría.

Por lo general, puede identificar este tipo de problemas visualizándolos como un árbol binario equilibrado. Por ejemplo, aquí está la ordenación de fusión:

 6   2    0   4    1   3     7   5
  2 6      0 4      1 3       5 7
    0 2 4 6            1 3 5 7
         0 1 2 3 4 5 6 7

En la parte superior se encuentra la entrada, como hojas del árbol. El algoritmo crea un nuevo nodo ordenando los dos nodos por encima de él. Sabemos que la altura de un árbol binario equilibrado es O (log n), por lo que hay O (log n) grandes pasos. Sin embargo, crear cada fila nueva requiere trabajo O (n). O (registro n) grandes pasos de trabajo O (n) significa que mergesort es O (n registro n) en general.

En general, los algoritmos O (log n) se parecen a la función siguiente. Llegan a descartar la mitad de los datos en cada paso.

def function(data, n):
    if n <= constant:
       return do_simple_case(data, n)
    if some_condition():
       function(data[:n/2], n / 2) # Recurse on first half of data
    else:
       function(data[n/2:], n - n / 2) # Recurse on second half of data

Mientras que los algoritmos O (n log n) se parecen a la función siguiente. También dividen los datos a la mitad, pero deben considerar ambas mitades.

def function(data, n):
    if n <= constant:
       return do_simple_case(data, n)
    part1 = function(data[n/2:], n / 2)      # Recurse on first half of data
    part2 = function(data[:n/2], n - n / 2)  # Recurse on second half of data
    return combine(part1, part2)

Donde do_simple_case () toma O (1) tiempo y combine () no toma más que O (n) tiempo.

Los algoritmos no necesitan dividir los datos exactamente a la mitad. Podrían dividirlo en un tercio y dos tercios, y eso estaría bien. Para un rendimiento promedio, basta con dividirlo en la mitad en promedio (como QuickSort). Siempre que la recursión se haga en piezas de (n / algo) y (n - n / algo), está bien. Si se está dividiendo en (k) y (nk), la altura del árbol será O (n) y no O (log n).

Answer 4

Intentaré hacer un análisis intuitivo de por qué Mergesort es n log n y, si me puede dar un ejemplo de un algoritmo n log log n, también puedo trabajar con él.

Mergesort es un ejemplo de clasificación que funciona mediante la división repetida de una lista de elementos hasta que solo existen elementos y luego se combinan estas listas. La operación principal en cada una de estas combinaciones es la comparación y cada combinación requiere a lo sumo n comparaciones donde n es la longitud de las dos listas combinadas. De esto puede derivar la recurrencia y resolverla fácilmente, pero evitaremos ese método.

En cambio, considere cómo se comportará Mergesort, vamos a tomar una lista y dividirla, luego tomar esas mitades y dividirla nuevamente, hasta que tengamos n particiones de longitud 1. Espero que sea fácil ver que esta recursión solo profundice en log (n) hasta que hayamos dividido la lista en n particiones.

Ahora que tenemos que cada una de estas n particiones tendrá que fusionarse, luego, una vez que se combinen, el siguiente nivel deberá fusionarse, hasta que tengamos una lista de longitud n nuevamente. Consulte el gráfico de wikipedia para ver un ejemplo simple de este proceso http://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg .

Ahora considere la cantidad de tiempo que tomará este proceso, vamos a tener niveles de registro (n) y en cada nivel tendremos que fusionar todas las listas. Resulta que cada nivel tardará n tiempo en fusionarse, porque estaremos fusionando un total de n elementos cada vez. Luego, puede ver fácilmente que tomará n tiempo de registro (n) ordenar una matriz con mergesort si considera que la operación de comparación es la operación más importante.

Si algo no está claro o salté en algún lugar, hágamelo saber y puedo tratar de ser más detallado.

Editar segunda explicación:

Déjame pensar si puedo explicar esto mejor.

El problema se divide en un montón de listas más pequeñas y luego las listas más pequeñas se ordenan y se combinan hasta que regrese a la lista original que ahora está ordenada.

Cuando rompa los problemas, primero tiene varios niveles diferentes de tamaño, tendrá dos listas de tamaño: n / 2, n / 2 y luego en el siguiente nivel tendrá cuatro listas de tamaño: n / 4, n / 4, n / 4, n / 4 en el siguiente nivel tendrás n / 8, n / 8, n / 8, n / 8, n / 8, n / 8, n / 8, n / 8, esto continúa hasta que n / 2 ^ k sea igual a 1 (cada subdivisión es la longitud dividida por una potencia de 2, no todas las longitudes serán divisibles entre cuatro, por lo que no será tan bonita). Esto se repite en la división por dos y puede continuar como máximo log_2 (n) veces, porque 2 ^ (log_2 (n)) = n, por lo que cualquier división más por 2 generaría una lista de tamaño cero.

Ahora, lo importante a tener en cuenta es que en cada nivel tenemos n elementos, por lo que para cada nivel la fusión llevará n tiempo, porque la fusión es una operación lineal. Si hay niveles de registro (n) de la recursión, realizaremos este registro de operación lineal (n) veces, por lo tanto, nuestro tiempo de ejecución será n registro (n).

Lo siento si eso tampoco es útil.

Answer 5

Para algunos algoritmos, obtener un límite estricto del tiempo de ejecución a través de la intuición es casi imposible (no creo que pueda intuir un tiempo de ejecución O(n log log n) , por ejemplo, y dudo que alguien siempre esperará que lo hagas). Si puede obtener el texto de Introducción a los algoritmos de CLRS , encontrará un tratamiento bastante completo de la notación asintótica que es apropiadamente riguroso sin ser completamente opaco.

Si el algoritmo es recursivo, una forma simple de derivar un límite es escribir una recurrencia y luego resolverlo, ya sea de forma iterativa o utilizando el Teorema Maestro o de alguna otra forma. Por ejemplo, si no busca ser súper riguroso al respecto, la forma más fácil de obtener el tiempo de ejecución de QuickSort es a través del Teorema Maestro: QuickSort implica la partición de la matriz en dos subarreglos relativamente iguales (debería ser bastante intuitivo ver que esto es O(n) , y luego llamar a QuickSort de forma recursiva en esos dos subarreglos. Luego, si permitimos que T(n) denote el tiempo de ejecución, tenemos T(n) = 2T(n/2) + O(n) , que por el Método Maestro es O(n log n) .

Answer 6

Por lo general, puede reclamar log n para algoritmos donde se divide el espacio / tiempo cada vez que se ejecuta. Un buen ejemplo de esto es cualquier algoritmo binario (por ejemplo, búsqueda binaria). Elije a la izquierda oa la derecha, que luego hace que el espacio que está buscando se reduzca a la mitad. El patrón de hacer la mitad repetidamente es log n.