Compte tenu d'une liste non formée de notes $ N $, combien de comparaisons aléatoires sont nécessaires en moyenne pour pouvoir trier la liste?

Question

Il y a une liste non formée de $ n $ articles $ x_1, \ ldots, x_n $ . Jusqu'à ce que vous puissiez trier la liste, vous recevez l'un des $ {n \ choisir 2} $ comparaisons binaires possibles uniformément au hasard (avec remplacement).

En moyenne, combien de ces comparaisons aléatoires devront-il pouvoir trier la liste?

Quelques questions de suivi:

1. Que doit ressembler à la distribution du nombre de comparaisons?
2. Quelle est la réponse si vous utilisez $ K $ -arisons au lieu de binaires.
3. Quelle est la réponse si les comparaisons sont effectuées sans remplacement (c'est-à-dire que vous n'obtiendrez pas la même comparaison deux fois)?
4. Compte tenu d'un ensemble de comparaisons, comment peut-on vérifier si la liste est capable? Je suis presque certain que la réponse est de construire un Dag et une sorte topologique, mais je veux juste confirmer.

Une réponse exacte-ish serait bien, mais une grosse classe $ o $ la réponse est bien aussi, je suppose.

Answer 1

Asympotiquement, vous aurez besoin $ \ theta (n ^ 2 \ journal n) $ comparaisons.

Supposons $ x _ {((1)}, \ points, x _ {(n)} $ désigne les éléments dans la commande triée. Ensuite, si vous ne voyez pas une comparaison entre $ x _ {((1)} $ et $ x _ {(2)} $ , vous n'aurez aucun moyen de dire à quel ordre ils devraient apparaître. Il en va de même de chaque paire d'élément adjacent. Donc, il y a $ N-1 $ coupons (une par paire d'éléments adjacents) et vous devez tous les recueillir. Basé sur le Coupon Collector Problème , nous savons que vous aurez besoin de $ \ theta (n \ journal n) $ Des coupons choisis au hasard avant de les avoir tous recueillis. Chaque observation a une $ 2 / N $ chance d'être un coupon, donc au total, nous aurons besoin $ \ theta (n ^ 2 \ journal n) $ observations avant que nous avons recueilli tous les coupons. Si nous collectons tous les coupons, nous pouvons trier la $ x $ 's; Si nous manquons un coupon, nous ne pouvons pas les trier.

Les questions suivantes bouchent sur des faits sur le problème du collecteur de coupon et vous pouvez utiliser les limites de la queue sur Wikipedia pour lier les informations sur la distribution.

Si les comparaisons sont choisies sans remplacement, alors vous avez besoin de $ \ theta (n ^ 2) $ observations.

Un moyen raisonnable de vérifier si la liste est trieuse consiste à effectuer un tri topologique, puis vérifiez que vous avez observé une comparaison entre chaque paire d'éléments adjacents dans l'ordre triés topologiquement.