sorting - top - reddit noticias

¿Cómo escribo un género peor que O(n!)

Question

Escribí un tipo O (n!) Para mi diversión que no se puede trivialmente optimizar para correr más rápido sin reemplazarlo por completo. [Y no, no solo asigné aleatoriamente los artículos hasta que fueron ordenados].

¿Cómo podría escribir un tipo Big-O aún peor, sin solo agregar basura extraña que podría extraerse para reducir la complejidad del tiempo?

http://en.wikipedia.org/wiki/Big_O_notation tiene varias complejidades de tiempo ordenadas en orden creciente.

Editar: encontré el código, aquí está mi orden determinista O (n!) Con truco divertido para generar una lista de todas las combinaciones de una lista. Tengo una versión ligeramente más larga de get_all_combinations que devuelve un iterable de combinaciones, pero desafortunadamente no pude convertirlo en una sola declaración. [Esperemos que no haya introducido errores al corregir errores tipográficos y quitar guiones bajos en el siguiente código]

def mysort(somelist):
for permutation in get_all_permutations(somelist):
if is_sorted(permutation):
return permutation
def is_sorted(somelist):
# note: this could be merged into return... something like return len(foo) <= 1 or reduce(barf)
if (len(somelist) <= 1): return True
return 1 > reduce(lambda x,y: max(x,y),map(cmp, somelist[:-1], somelist[1:]))
def get_all_permutations(lst):
return [[itm] + cbo for idx, itm in enumerate(lst) for cbo in get_all_permutations(lst[:idx] + lst[idx+1:])] or [lst]

Answer 1

Creo que si haces muchas copias entonces puedes obtener una búsqueda de fuerza bruta "razonable" (N!) Para tomar N ^ 2 veces por caso dando N! * N ^ 2

Answer 2

Existe un (peor) algoritmo de clasificación llamado " tipo lento" que usa el paradigma "multiplicar y rendirse" y se ejecuta en tiempo exponencial.

Si bien su algoritmo es más lento, no progresa de manera constante, sino que realiza saltos aleatorios. Además, el mejor caso de clasificación lenta sigue siendo exponencial mientras que el tuyo es constante.

Answer 3

Siempre hay NeverSort, que es O (∞):

def never_sort(array)
while(true)
end
return quicksort(array)
end

PD: ¡Realmente quiero ver tu tipo determinista O (n!); No puedo pensar en ninguno que sea O (n!), Pero tenga un límite superior finito en computación clásica (también conocido como determinista).

PPS: si le preocupa que el compilador borre ese bloque vacío mientras lo está haciendo, puede forzarlo a no hacerlo mediante el uso de una variable dentro y fuera del bloque:

def never_sort(array)
i=0
while(true) { i += 1 }
puts "done with loop after #{i} iterations!"
return quicksort(array)
end

Answer 4

Una forma en que puedo pensar sería calcular la posición de publicación de cada elemento a través de una función que varía moviendo gradualmente los elementos grandes al final y los pequeños al principio. Si utilizó una función basada en trigonometría, puede hacer que los elementos se desplacen a través de la lista en lugar de ir directamente hacia su posición final. Después de que haya procesado cada elemento en el conjunto, haga un recorrido completo para determinar si la matriz está ordenada o no.

No estoy seguro de que esto te dé O (n!) Pero aún así debería ser bastante lento.

Answer 5

¿Qué hay de bucle sobre todas las matrices t de n enteros (n-tuplas de enteros son contables, por lo que esto es factible, aunque es un ciclo infinito, por supuesto), y para cada uno de estos:

• si sus elementos son exactamente los de la matriz de entrada (ver algo más abajo) y la matriz está ordenada (algo lineal, por ejemplo, pero estoy seguro de que podemos hacerlo peor), entonces devuelve t;
• de lo contrario, continúe bucleando.

Para comprobar que dos matrices a y b de longitud n contienen los mismos elementos, ¿qué le parece el siguiente algoritmo recursivo: bucle sobre todas las parejas (i, j) de índices entre 0 y n-1, y para cada pareja

• prueba si a [i] == b [j]:
• de ser así, devuelva TRUE si y solo si una llamada recursiva en las listas obtenidas al eliminar un [i] de ayb [j] de b devuelve VERDADERO;
• continúe dando vueltas sobre las parejas, y si todas las parejas terminan, devuelva FALSO.

El tiempo dependerá mucho de la distribución de los enteros en la matriz de entrada.

En serio, sin embargo, ¿hay un punto para tal pregunta?

Editar:

@Jon, tu clasificación aleatoria estaría en O (n!) En promedio (ya que hay n! Permutaciones, tienes probabilidad 1 / n! De encontrar la correcta). Esto se aplica a las matrices de enteros distintos, puede ser ligeramente diferente si algunos elementos tienen múltiples ocurrencias en la matriz de entrada, y luego dependerá de la distribución de los elementos de las matrices de entrada (en los enteros).

Answer 6

Siempre puedes hacer un orden aleatorio. Funciona reorganizando todos los elementos aleatoriamente, luego verificando si está ordenado. Si no, los visita al azar. No sé cómo encajaría en la notación de O grande, ¡pero definitivamente será lento!

Answer 7

Aquí está el tipo más lento y finito que puede obtener:

Enlace cada operación de Quicksort a la función Busy Beaver.

En el momento en que obtienes> 4 operaciones, necesitarás notación con flecha hacia arriba :)

Answer 8

Chris y yo mencionamos a Bozosort y Bogosort en una pregunta diferente.