¿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 ejecutarlo 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: He encontrado el código, aquí está mi orden determinista O (n!) Con divertido truco para generar la 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. [Con suerte no he introducido errores mediante la fijación de los errores tipográficos y la eliminación de guiones en el código de abajo]

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

Chris y yo mencionado Bozosort y Bogosort de una manera different question.

Answer 2

Uno que se me ocurre sería Calculamos 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 comienzo. 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 3

Siempre hay NeverSort, que es O (∞):

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

PD: Tengo muchas ganas de ver a su determinista O (n) es un género; 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 usted está preocupado por el compilador acabando con que se vacían mientras que el bloque, puede forzar a que no mediante el uso de una variable, tanto dentro como 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

creo que si usted hace muchas copias y luego puede obtener una búsqueda de fuerza bruta "razonable" (N!) para obtener N^2 veces por caso dando N! * N^2

Answer 5

Hay un (peor) algoritmo de clasificación conocido como slow sort que usa el paradigma de "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 6

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

• si su los 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), y luego devuelve t;
• de lo contrario, continúe el bucle.

para comprobar que dos matrices A y B de longitud n contienen los mismos elementos, cómo sobre el siguiente algoritmo recursivo: bucle sobre todas las parejas (i, j) de los índices de entre 0 y n-1, y para cada tal par prueba

• si a [i] == b [j]:
• si es así, devolver TRUE si y sólo si una llamada recursiva en las listas que se obtiene eliminando a [i] de a y b [j] de b devuelve VERDADERO;
• continúe girando sobre las parejas, y si todas las parejas han terminado, devuelva FALSO.

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

Hablando en serio, ¿hay algún punto para tal pregunta?

Editar:

@ Jon, su tipo al azar sería en O (n!) En promedio (ya que hay n permutaciones, que tienen 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 7

Siempre se puede 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 8

Aquí es el tipo más lento, finita puede obtener:

Enlace cada operación de ordenación rápida a la función del castor ocupado.

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