Bogosort es solo la punta del iceberg. Hagamos un viaje mucho más profundo hacia el abismo.
Peor
es un algoritmo de ordenación pesimista que se garantiza que se complete, suponiendo que el universo no se queme antes de completar el algoritmo; sin embargo, no existe un límite computable para la ineficiencia del algoritmo de clasificación y, por lo tanto, es más pesimista que los otros algoritmos descritos aquí. El algoritmo [math] {\ displaystyle {\ text {worstsort}}} [/ math] se basa en un algoritmo de clasificación incorrecto, [math] {\ displaystyle {\ text {badsort}}} [/ math]. El algoritmo badsort acepta dos parámetros: [math] {\ displaystyle L} [/ math], que es la lista que se va a ordenar, y [math] {\ displaystyle k} [/ math], que es una profundidad de recursión. En el nivel de recursión [math] {\ displaystyle k = 0} [/ math], [math] {\ displaystyle {\ text {badsort}}} [/ math] simplemente usa un algoritmo de ordenación común, como bubbleort, para ordenar su entradas y devolver la lista ordenada. Es decir, [matemáticas] {\ displaystyle {\ text {badsort}} (L, 0) = {\ text {bubblesort}} (L)} [/ math]. Por lo tanto, la complejidad temporal de badsort es [matemática] {\ displaystyle O \ left (n ^ {2} \ right)} [/ math] if [math] {\ displaystyle k = 0} [/ math]. Sin embargo, para cualquier [math] {\ displaystyle k> 0} [/ math], [math] {\ displaystyle {\ text {badsort}} (L, k)} [/ math] genera primero [math] {\ displaystyle P} [/ math], la lista de todas las permutaciones de [math] {\ displaystyle L} [/ math]. Luego, [math] {\ displaystyle {\ text {badsort}}} [/ math] calcula [math] {\ displaystyle {\ text {badsort}} (P, k-1)} [/ math], y devuelve el primer elemento de la ordenada [matemática] {\ displaystyle P} [/ matemática]. Para hacer que [math] {\ displaystyle {\ text {worstsort}}} [/ math] sea realmente pesimista, [math] {\ displaystyle k} [/ math] puede asignarse al valor de una función creciente computable como [math] ] {\ displaystyle f \ colon \ mathbb {N} \ to \ mathbb {N}} [/ math] (por ejemplo, [math] {\ displaystyle f (n) = A (n, n)} [/ math], donde [matemáticas] {\ displaystyle A} [/ matemáticas] es la función de Ackermann). Ergo, para ordenar una lista arbitrariamente mal, ejecutarías [matemáticas] {\ displaystyle {\ text {worstsort}} (L, f) = {\ text {badsort}} (L, f ({\ text {length}} (L)))} [/ math], donde [math] {\ displaystyle {\ text {length}} (L)} [/ math] = número de elementos en [math] {\ displaystyle L} [/ math] . El algoritmo resultante tiene complejidad [matemática] {\ displaystyle \ Omega \ left (\ left (n! ^ {(F (n))} \ right) ^ {2} \ right)} [/ math], donde [math] {\ displaystyle n! ^ {(m)} = (\ dotso ((n!)!)! \ dotso)!} [/ math] = factorial de [math] {\ displaystyle n} [/ math] iterado [math ] {\ displaystyle m} [/ math] veces. Este algoritmo puede hacerse tan ineficiente como lo deseemos eligiendo una función de crecimiento lo suficientemente rápida [matemática] {\ displaystyle f} [/ matemática].
- ¿Qué son los pseudocódigos para GCD?
- ¿Cómo podría encontrar la métrica correcta que se utilizará para los vecinos más cercanos u otros algoritmos basados en similitudes?
- ¿Cuál es exactamente la diferencia entre f (n) yg (n)?
- Según Knuth, un algoritmo puede tener cero o más entradas. ¿Alguien puede darme un ejemplo de un algoritmo sin entrada?
- Cómo hacer un bot de chat usando Python implementando algoritmos de aprendizaje automático (como SVM, Naive Bayes, Random Forest, etc.)
[8]
Citado de Bogosort – Wikipedia
