Quelle est la complexité temporelle de la sorte de sommeil?

Question

Étant donné cet algorithme de tri, comment exprimez-vous sa complexité temporelle?

Présenté à l'origine ici

 #!/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

O(max(input)+n)

La complexité semble simplement difficile à exprimer, car la plupart des algorithmes de tri ne tiennent pas compte des données. Leur temps dépend de la quantité de données, pas des données elles-mêmes.

Comme indiqué ici , FWIW n’est pas un algorithme fiable pour le tri des données.

Answer 2

Personne ne semble avoir abordé le problème de la mise en œuvre de ces sleep s. En fin de compte, ils se retrouvent quelque part dans un planificateur, et la complexité opérationnelle dépendra de l'algorithme de planification utilisé. Par exemple, si les sleep s sont placés en tant qu'événements dans une file d'attente prioritaire, vous obtiendrez probablement quelque chose d'équivalent à Heapsort, de complexité O (n log n) . Un algorithme d'ordonnancement naïf pourrait donner O (n ^ 2) .

Answer 3

Je pense que paxdiablo est plus proche, mais pas pour les bonnes raisons. Le temps de la complexité ignore les questions sur le matériel réel telles que les tailles de cache, les limites de la mémoire et dans ce cas, le nombre limité de processus et le fonctionnement de l'ordonnanceur.

Fondée sur la page de Wikipedia pour le Temps de la complexité , je dirais que la réponse est que vous ne pouvez pas déterminer à l'exécution de la complexité, car si elle est définie comme:

Complexité temporelle est communément estimée par comptage du nombre d'opérations élémentaires effectuées par l'algorithme, où une opération élémentaire prend un montant fixe de temps à effectuer. Ainsi, le temps passé et le nombre d'opérations élémentaires effectuées par l'algorithme diffèrent par au plus un facteur constant.

Puis on ne peut pas parler de l'exécution de la complexité de cet algorithme, car l'heure laquelle les opérations élémentaires à prendre est bien différent, que le temps serait diffèrent de plus d'un facteur constant.

Answer 4

À la fois la complexité du temps et le processus de la complexité de cet algorithme sont O(braindead).

Avec une assez grande valeur dans l'ensemble de données, vous serez en attente d'une réponse, jusqu'à ce que le soleil explose.

Avec un suffisamment grand ensemble de données de taille, vous verrez

• (1) atteint votre limite de processus; et
• (2) trouver que les premiers dort tout sera fini avant les dernières commencer, sens de l'ensemble (2,9,9,9,9,9,...,9,9,1) ne sorte de l' 1 et 2 correctement.

Le temps de la complexité n'est pas pertinent dans ce cas. Vous ne pouvez pas obtenir moins optimisé que le "mal".

C'est correct d'utiliser l'analyse de la complexité de comparer les algorithmes que l'ensemble de données, les changements de taille, mais pas lorsque les algorithmes sont ridicule en premier lieu :-)

Answer 5

Mise à jour: j'ai reviennent à la conclusion qu' O(m+n)où n est la longueur de la liste, m est le plus grand élément, il est en fait saine.

Original suit la réponse.

---

justinhj la réponse est assez bonne, mais je ne crois pas qu'il a raison en disant que vous ne pouvez pas déterminer à l'exécution de la complexité.

Rappelez-vous lors du calcul du pire des cas le temps de complexité qu'il est le pire des cas le temps de la complexité. Vous ne pouvez pas faire d'hypothèses sur la taille de l'entrée; vous devez le prendre en compte à l'infiniment grand. "L'infini" de quelle manière, selon le type de l'entrée (et la façon dont il est utilisé, vous voulez penser à ce qui prend le plus de temps, donc, dans certains cas, l'inverse est pris, cette "infini" peut-être plutôt quelque chose de proche de zéro plutôt que de l'infini). Pour quelque chose de prendre une liste, qui sera généralement une liste avec infiniment de nombreux éléments. Pour quelque chose de prendre un certain nombre, qui sera généralement ∞ (ci - inf).

Par ce raisonnement correct, les réponses qui suggèrent O(max(input) + n) sont défectueuses. Mais encore, il est possible de calculer la complexité, si elle est utile ou valable ou pas.

Lors de l'examen de cet algorithme, clairement l'élément qui est à l'origine des problèmes est - sleep. Le reste est facile à calculer, il se termine à l' O(n+sleep), avec la connaissance qu'il n'a pas d'importance combien de fois vous êtes en cours d'exécution sleep, leur temps sera indépendante (le temps de la complexité careth pas pour un peu louches planificateur de tâches ou un nombre maximal de processus qui peuvent être exécutés ou en cours d'exécution hors de la mémoire—ou autre chose, vous pouvez facilement appeler tout O(1)). Mais qu'est - sleep's le temps de la complexité? Rappelez-vous, vous devez tenir compte de la contribution qui prend le plus de temps. C'est, pour le sommeil, un infiniment grand nombre. Ainsi, sleep est, avec des constantes encore en, O(inf). Alors la question importante: est - inf d'une constante? Si elle l'est, sleep est O(1); si elle ne l'est pas, sleep encore O(inf). Quoi qu'il en soit, il ne peut y avoir de simplification de la complexité de l' sleep tel qu'il apparaît dans l'algorithme que les entrées doivent être supposé infiniment grand.

Alors, qui est-il? Est - inf une constante, ou pas?

Je vous présente alors avec deux réponses possibles à la fois de la complexité de l' sleepsort.bash:

• O(n) (si inf est une constante)
• O(inf+n) (si inf n'est pas une constante)

Qui allez-vous aller? Pour moi, je crois que je préfère l'ancien.