algorithm - saludables - ¿Es correcto el análisis de FrogSort en el Cereal de desayuno del sábado por la mañana?

los mejores cereales para adelgazar

Question

En un reciente comic de Cereales para el desayuno del sábado por la mañana , el autor describe un algoritmo llamado Frog Sort para clasificar una lista de números naturales. El algoritmo se describe en el cómic, pero por simplicidad lo he reproducido aquí:

1. Para cada uno de los números naturales a clasificar, haga una caja con tantas moscas.
2. Pon una rana en cada caja.
3. Si bien no todas las ranas han saltado de sus cajas todavía:
   1. Espera a que salte una rana de su caja.
   2. Anote la cantidad de moscas originalmente colocadas en la caja.
4. La secuencia resultante de números es la lista original de números, pero en orden ordenado.

Este algoritmo asume que todas las ranas comen moscas al mismo ritmo. Como resultado, la primera rana que salte de su caja será la rana que tenga la menor cantidad de moscas que cada una, la segunda rana será la segunda que menos moscas para comer, etc.

En medio del cómic, un profesor pregunta a los alumnos "¿Qué es el número máximo de pasos?", Lo que interpreto como "¿cuál es el número máximo de pasos necesarios para que termine este algoritmo ?;" es decir, ¿cuál es el tiempo de ejecución del algoritmo? El estudiante entonces responde "log _rana (cajas)".

¿Es este un análisis preciso del tiempo de ejecución de este algoritmo? ¿O está equivocado el autor?

Answer 1

Esto no es una respuesta, pero a Zach mismo le gustó esto. Es parte de un huevo de pascua en el lenguaje de programación esotérico cbrain, http://esolangs.org/wiki/Cbrain . Un derivado de bf, compilado con OpenCOBOL. Para estar fuera de la rana, el valor condicional justo podría establecerse en 2 en lugar de 1. frogSort en COBOL.

      *> ********************************************************
      *>  frogSort, called for help with 10-94, request for count
      *> ********************************************************
       identification division.
       program-id. frogsort.
       data division.
       working-storage section.
       01 opinion          usage binary-long.
       01 shared-value     pic 99.
          88 fair          value 1.
       01 caveman-count    pic x(12) value "[-]+++++++++".
       01 spacer           pic x(10) value spaces.

       linkage section.
       01 jars.
          05 flies        pic 9 occurs 21 times.

      *> ********************************************************
       procedure division using jars.
       start-here.
       move function length(jars) to shared-value
       display "Grog sort jars.  frogSort" end-display
       display "http://www.smbc-comics.com/?id=2831" end-display
       .

       forkyourself.
           call "fork" returning opinion end-call
           if opinion is zero then
               subtract 1 from shared-value
               if not fair then go forkyourself.
       .

       call "sleep" using by value flies(shared-value) end-call
       display
           "Jar: " function char(shared-value + 65) " reporting "
           caveman-count(1 : flies(shared-value) + 3) " flies,"
           spacer(1 : 10 - flies(shared-value))
           "that would be " flies(shared-value) " to you, futureman."
       end-display
       call "wait" using by value 0 end-call

       stop run returning 107.
       end program frogsort.

con el huevo de Pascua pateado con CALL "frogsort" USING "" 012345678901234567890 "END-CALL

$ ./cbrainrun 
10-12 Welcome to cbrain v0.42
cb: 1094
cb: help
Grog sort jars.  frogSort
http://www.smbc-comics.com/?id=2831
Jar: U reporting [-] flies,          that would be 0 to you, futureman.
Jar: K reporting [-] flies,          that would be 0 to you, futureman.
Jar: A reporting [-] flies,          that would be 0 to you, futureman.
Jar: L reporting [-]+ flies,         that would be 1 to you, futureman.
Jar: B reporting [-]+ flies,         that would be 1 to you, futureman.
Jar: M reporting [-]++ flies,        that would be 2 to you, futureman.
Jar: C reporting [-]++ flies,        that would be 2 to you, futureman.
Jar: N reporting [-]+++ flies,       that would be 3 to you, futureman.
Jar: D reporting [-]+++ flies,       that would be 3 to you, futureman.
Jar: O reporting [-]++++ flies,      that would be 4 to you, futureman.
Jar: E reporting [-]++++ flies,      that would be 4 to you, futureman.
Jar: P reporting [-]+++++ flies,     that would be 5 to you, futureman.
Jar: F reporting [-]+++++ flies,     that would be 5 to you, futureman.
Jar: Q reporting [-]++++++ flies,    that would be 6 to you, futureman.
Jar: G reporting [-]++++++ flies,    that would be 6 to you, futureman.
Jar: R reporting [-]+++++++ flies,   that would be 7 to you, futureman.
Jar: H reporting [-]+++++++ flies,   that would be 7 to you, futureman.
Jar: S reporting [-]++++++++ flies,  that would be 8 to you, futureman.
Jar: I reporting [-]++++++++ flies,  that would be 8 to you, futureman.
Jar: T reporting [-]+++++++++ flies, that would be 9 to you, futureman.
Jar: J reporting [-]+++++++++ flies, that would be 9 to you, futureman.

Answer 2

Estoy bastante seguro de que el autor del cómic está equivocado. A continuación se muestra un análisis más formal del algoritmo.

Para empezar, tendremos que establecer algunas reglas básicas sobre cómo las ranas comen moscas. Asumiré que todas las ranas pueden comer moscas a una velocidad constante r. Es decir, toma r segundos para que una rana se coma una mosca, 10r segundos para que una rana coma diez moscas, etc. Luego, supongamos (razonable) que todas las ranas comen en paralelo. También asumiremos que se necesita tiempo para que una rana salte de una caja vacía.

También necesitamos tener en cuenta el tiempo de configuración. Supongamos que tenemos un suministro ilimitado de moscas, ranas y cajas, y digamos que se necesita b tiempo para obtener una caja y y tiempo para poner una sola mosca en una caja. Finalmente, asumiremos que lleva tiempo poner una rana en una caja. Para simplificar, supondremos que las ranas no comienzan a comer moscas hasta que se las indiquemos explícitamente, de modo que las ranas colocadas en cajas antes de que otras ranas no tengan una ventaja inicial.

Un último detalle: supongamos que lleva tiempo escribir un número.

En ese caso, el tiempo de ejecución de este algoritmo se da de la siguiente manera. Supongamos que nuestra lista de números a ordenar es x ₁ , x ₂ , ..., x _n . En ese caso, el tiempo requerido para configurar todas las casillas será n (b + f) + y (Σx _i ). La razón de esto es que necesitamos obtener n cajas y poner una rana en cada caja (de ahí el primer término), más y y unidades de tiempo para cada una de las moscas (de ahí el segundo término).

En el curso del algoritmo, tendremos que anotar cada número exactamente una vez, cuando la rana salte de su caja. Esto significa que en todo el algoritmo, haremos un nuevo trabajo escribiendo la secuencia ordenada.

Finalmente, tenemos que considerar cuánto tardan todas las ranas en terminar. Dado que todas las ranas comen en paralelo, todo lo que debemos cuidar es la rana que tiene la mayor cantidad de moscas para comer. Esta rana tendrá x _max moscas para comer, donde x _max es el número máximo en la lista de entrada. Por lo tanto, el tiempo _{máximo que} dedican las ranas a comer es dado por rx _max . Al tomar en cuenta el salto realizado por la última rana, las ranas, todas trabajando en paralelo, terminarán colectivamente en rx _max + j time.

Esto significa que el tiempo total para el algoritmo viene dado por

n (f + b) + yΣx _i + nw + rx _max + j.

Si ahora asumimos que "una unidad de trabajo" será suficiente para realizar cualquiera de las operaciones individuales (haga que una rana coma una mosca, salte de una caja o ponga una rana en una caja, etc.), el total el tiempo requerido es como máximo

n + Σ (x _i ) + x _max + 1

Observando que x _max ≤ Σx _i , obtenemos que el tiempo de ejecución total de este algoritmo es Θ (n + Σx _i ). En otras palabras, el tiempo de ejecución es proporcional tanto al número de números para ordenar, como al tamaño total de los números a ordenar.

Tenga en cuenta que este tiempo de ejecución no tiene logaritmos, por lo que podemos concluir inmediatamente que el análisis del tiempo de ejecución del autor es incorrecto.

Finalmente, tenga en cuenta que este es un algoritmo de clasificación realmente malo. El algoritmo de clasificación de conteo podría ordenar n números naturales en el tiempo O (n + U), donde U es el valor máximo a clasificar, que es asintóticamente mejor que FrogSort. El algoritmo de clasificación de radix podría hacer esto en tiempo O (n lg U), que es mejor para valores grandes de U. Por otra parte, ambos algoritmos requieren una maquinaria sofisticada, que probablemente no existiría en la configuración descrita por el cómic.

¡Espero que esto ayude!

Answer 3

Este análisis de tiempo de ejecución es claramente incorrecto; podemos obtener un tiempo de ejecución trivial de max(n_elements, largest_element) (ya que tenemos n_elements , y luego cada cuadro tarda tanto en vaciarse como el tamaño de su contenido). Un algoritmo de clasificación que tomara menos de n tiempo sería ... muy sorprendente.

Si desea encontrar más análisis en Internet en algún lugar, este algoritmo es equivalente a la ordenación del sueño. En caso de que no esté familiarizado con ese algoritmo ridículo, aquí está en bash:

#!/bin/bash

function sort() {
    for num in "$@" ; do
        (
        sleep $num
        echo $num
        ) &
    done
    wait
}

sort 6 1 3 4