time-complexity - how - time complexity calculator

¿Cuál es la complejidad del tiempo del tipo de sueño?

Question

Dado este algoritmo de ordenamiento, ¿cómo expresas su complejidad temporal?

Originalmente presentado aquí (archivo parcial) .

#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7

Answer 1

Aunque parece lineal, creo que la complejidad sigue siendo O (log (n) * max (entrada)).

Cuando hablamos de complejidad de tiempo asintótica, significa cuánto tiempo se tarda cuando n crece infinitamente grande.

Un algoritmo de clasificación basado en comparaciones no puede ser más rápido que O (n * log (n)), y Sleep-Sort, en realidad está basado en comparaciones:

Los procesos duermen en segundos y despiertan. El sistema operativo necesita encontrar el tiempo de sueño menos importante de todos los procesos de sueño, y despertarlo si ya es hora.

Esto necesitará una cola de prioridad, que toma el tiempo O (logN) insertando un elemento, y O (1) buscando el elemento mínimo, y O (logN) eliminando el elemento mínimo.

Cuando n es muy grande, tardará más de 1 segundo en reactivar un proceso, lo que lo hace más grande que O (n).

Answer 2

Creo que paxdiablo es el más cercano, pero no por la razón correcta. La complejidad del tiempo ignora los problemas en el hardware real, como los tamaños de caché, los límites de memoria y, en este caso, el número limitado de procesos y el funcionamiento del programador.

Basado en la página de Wikipedia para la complejidad del tiempo , diría que la respuesta es que no se puede determinar la complejidad del tiempo de ejecución porque si se define como:

La complejidad del tiempo se suele calcular contando el número de operaciones elementales realizadas por el algoritmo, donde una operación elemental lleva una cantidad de tiempo fija. Por lo tanto, la cantidad de tiempo empleado y el número de operaciones elementales realizadas por el algoritmo difieren en un máximo de un factor constante.

Entonces no podemos hablar sobre la complejidad del tiempo de ejecución de este algoritmo porque el tiempo que toman las operaciones elementales es tan enormemente diferente, que el tiempo empleado diferiría en más que un factor constante.

Answer 3

Estoy con Jordan, excepto que creo que la complejidad del tiempo de pared se expresa mejor como O (2 ^ m) donde m es el tamaño de cada elemento, en lugar de O (máximo (entrada)).

Si cada elemento tiene un tamaño m, el elemento más grande tendrá un valor entero de 2 ^ m (menos uno, pero a nadie le importa). Por construcción, el algoritmo requiere que el tiempo de configuración sea menor que 1, una constante.

Entonces, la complejidad del reloj de pared O (2 ^ m), la complejidad del recuento de operaciones O (n).

Un algoritmo modificado que tenga en cuenta el tiempo de establecimiento probablemente tenga una complejidad de tiempo de pared-reloj O (2 ^ m + n). Por ejemplo, podría tener en cuenta la hora actual al comienzo, calcular base_time = start_time + k*len(list) (para alguna constante apropiada k), luego hacer que los hilos duerman hasta el tiempo base_time+i . Entonces k*len(list) es claramente O (n) i es O (2 ^ m) como antes, para un total de O (2 ^ m + n).

Answer 4

Si lees el hilo, verás que tu pregunta ya está respondida. La complejidad del tiempo es O(max(input)) y la complejidad operacional (cantidad de operaciones) es O(n) .

Answer 5

Tanto la complejidad del tiempo como la complejidad del proceso de ese algoritmo son O(braindead) .

Con un valor suficientemente grande en el conjunto de datos, estará esperando una respuesta hasta que el sol explote.

Con un tamaño de conjunto de datos suficientemente grande , podrás

• (1) alcance su límite de proceso; y
• (2) descubra que los (2,9,9,9,9,9,...,9,9,1) tempranos terminarán antes de que comiencen los últimos, lo que significa que el conjunto (2,9,9,9,9,9,...,9,9,1) no ordenará correctamente el 1 y el 2 .

La complejidad del tiempo es irrelevante en este caso. No se puede obtener menos optimizado que "incorrecto".

Está bien utilizar el análisis de complejidad para comparar algoritmos a medida que cambia el tamaño del conjunto de datos, pero no cuando los algoritmos son absurdos en primer lugar :-)

Answer 6

Un punto que nadie parece haber abordado es cómo se implementan esos sleep . En última instancia, terminan en un programador en alguna parte, y la complejidad operativa dependerá del algoritmo de programación utilizado. Por ejemplo, si los sleep s se colocan como eventos en una cola de prioridad, es probable que termine con algo equivalente a heapsort, con complejidad O (n log n) . Un algoritmo de programación ingenuo podría dar como resultado O (n ^ 2) .

Answer 7

O(max(input)+n)

La complejidad simplemente parece incómoda de expresar porque la mayoría de los algoritmos de clasificación son independientes de los datos. Su tiempo se basa en la cantidad de datos, no en los datos en sí.

FWIW, como se señala here , este no es un algoritmo confiable para clasificar datos.