Quelle est la valeur O pour la sélection aléatoire naïve de jeu fini?

Question

Cette question sur l'obtention de valeurs aléatoires à partir d'un ensemble fini m'a fait penser ...

Il est assez fréquent que les gens veulent récupérer les valeurs uniques X à partir d'un ensemble de valeurs Y. Par exemple, je veux traiter une main d'un jeu de cartes. Je veux 5 cartes, et je veux qu'ils être uniques.

Maintenant, je peux le faire naïvement, en choisissant une carte au hasard 5 fois, et essayez à nouveau chaque fois que je reçois un double, jusqu'à ce que je reçois 5 cartes. Ce n'est pas si grand, cependant, pour un grand nombre de valeurs de grands ensembles. Si je voulais 999.999 valeurs d'un ensemble de 1000000, par exemple, cette méthode devient très mauvais.

La question est: à quel point? Je cherche quelqu'un pour expliquer une valeur O (). Obtenir le nombre Xème prendra les tentatives y ... mais combien? Je sais comment comprendre cela pour une valeur donnée, mais est-il un moyen simple de généraliser ce pour toute la série et obtenir une valeur O ()?

(La question est: « comment puis-je améliorer cela? », Car il est relativement facile de fixer, et je suis sûr qu'il a été couvert à plusieurs reprises ailleurs.)

Answer 1

Variables

n = la quantité totale d'éléments dans l'ensemble
m = la quantité de valeurs uniques qui doivent être récupérées à partir de l'ensemble des n éléments
d (i) = la quantité attendue d'essais nécessaires pour atteindre une valeur dans l'étape i
i = représente une étape spécifique. i ∈ [0, n-1]
T (m, n) = quantité totale attendue des essais de sélection m des objets uniques à partir d'un ensemble de n objets en utilisant l'algorithme naïf

Raisonnement

La première étape, i = 0, est triviale. Quelle que soit la valeur que nous choisissons, nous obtenons un unique à la première tentative. Par conséquent:

d (0) = 1

Dans la deuxième étape, i = 1, nous avons au moins besoin d'essayer 1 (l'essai dans lequel on choisit une valeur unique valide). En plus de cela, il y a une chance que nous choisissons la valeur erronée. Cette chance est (quantité d'articles précédemment cueillis) / (quantité totale d'articles). Dans ce cas, 1 / n. Dans le cas où nous avons choisi le mauvais article, il y a une chance 1 / n on peut choisir à nouveau le mauvais article. Multipliant par 1 / n, puisque c'est la probabilité combinée que nous prenons mal deux fois, donne (1 / n) ² . Pour comprendre cela, il est utile de faire un séquence géométrique et, par conséquent, il est facile de le calculer est la somme:

d (i) = (1 - i / n) ^-1

La complexité globale est ensuite calculée en additionnant la quantité attendue d'essais dans chaque étape:

T (m, n) = somme (d (i)), où i ∈ [0, m-1] =
= 1 + (1 - 1 / n) ^-1 + (1 - 2 / n) ^-1 + (1 - 3 / n) ^-1 + ... + (1 - (m-1) / n ) ^-1

L'extension des fractions de la série ci-dessus par n, nous obtenons:

T (m, n) = n / n + n / (n-1) + n / (n-2) + n / (n-3) + ... + n / (n-m + 2 ) + n / (n-m + 1)

On peut utiliser le fait que:

n / n ≤ n / (n-1) ≤ n / (n-2) ≤ n / (n-3) ≤ ... ≤ n / (n-m + 2) ≤ n / (n- m + 1)

Étant donné que la série a m termes, et chaque terme satisfait à l'inégalité ci-dessus, nous obtenons:

T (m, n) ≤ n / (n-m + 1) + n / (n-m + 1) + n / (n-m + 1) + n / (n-m + 1) + ... + n / (n-m + 1) + n / (n-m + 1) =
= m * n / (n-m + 1)

Il est peut-être (et est probablement) possible d'établir une limite supérieure légèrement plus stricte liée en utilisant une technique pour évaluer la série au lieu de englobante par la méthode approximative (quantité de termes) * (le plus grand terme)

Conclusion

Cela signifie que l'ordre Big-O est O (m * n / (n-m + 1)) . Je ne vois aucun moyen possible de simplifier cette expression de la façon dont il est.

Revenant sur le résultat à vérifier s'il est logique , nous voyons que, si n est constant, et m se rapproche et plus proche de n, les résultats augmentent rapidement, puisque le dénominateur obtient très petit. Voilà ce que nous attendrions, si nous considérons par exemple l'exemple donné dans la question sur le choix « 999.999 valeurs d'un ensemble de 1000000 ». Si nous laissons la place m soit constante et n grandir vraiment, vraiment grande, la complexité va converger vers O (m) dans la limite n → ∞. C'est aussi ce que nousd attendre, puisque tout en choisissant un nombre constant d'éléments d'un « proche de » infiniment dimensionnées définir la probabilité de choisir une valeur choisie précédemment est essentiellement 0. à savoir Nous avons besoin de m tente indépendamment de n car il n'y a pas de collisions.

Answer 2

Si vous avez déjà choisi des valeurs i alors la probabilité que vous choisissez un nouveau à partir d'un ensemble de valeurs y est

(y-i)/y.

D'où le nombre prévu d'essais pour obtenir (i + 1) -ième élément est

y/(y-i).

Ainsi, le nombre prévu d'essais pour choisir x élément unique est la somme

 y/y + y/(y-1) + ... + y/(y-x+1)

Cela peut être exprimé en utilisant nombres harmoniques comme

  

y. (H _y - H _y-x )

Dans la page wikipedia vous obtenez l'approximation

  

H _x = ln (x) + gamma + O (1 / x)

D'où le nombre d'essais nécessaires pour choisir x éléments uniques à partir d'un ensemble d'éléments y est

y (ln(y) - ln(y-x)) + O(y/(y-x)).

Si vous avez besoin alors vous pouvez obtenir une approximation plus précise en utilisant une approximation plus précise pour H _x . En particulier, lorsque x est petit, il est possible de améliorer le résultat beaucoup.

Answer 3

Votre question réelle est en fait beaucoup plus intéressant que ce que je répondais (et plus difficile). Je ne l'ai jamais été bon à statistitcs (et ça a été un moment que je l'ai fait tout), mais intuitivement, je dirais que la complexité d'exécution de cet algorithme serait probablement quelque chose comme une exponentielle. Tant que le nombre d'éléments cueillis est assez petit par rapport à la taille du tableau le taux de collision sera si petit qu'il sera proche de temps linéaire, mais à un moment donné le nombre de collisions va probablement croître rapidement et la course -temps descendrai le drain.

Si vous voulez prouver, je pense que vous auriez à faire quelque chose modérément intelligent avec le nombre prévu de collisions en fonction du nombre voulu d'éléments. Il pourrait être possible de le faire par induction, mais je pense aller par cette voie, il faudrait plus que l'intelligence la première alternative.

EDIT: Après avoir réfléchi, voici ma tentative:

Dans une série d'éléments de m, et la recherche de n éléments aléatoires et différents. Il est alors facile de voir que lorsque l'on veut choisir l'élément ith, les chances de choisir un élément que nous avons déjà visité sont (i-1)/m. Voici donc le nombre prévu de collisions pour ce choix particulier. Pour choisir des éléments de n, le nombre prévu de collisions sera la somme du nombre de collisions attendues pour chaque choix. Nous brancher sur Wolfram Alpha (somme (i-1) / m, i = 1 à n) et nous obtenons la (n**2 - n)/2m de réponse. Le nombre moyen de choix pour notre algorithme naïf est alors n + (n**2 - n)/2m.

À moins que ma mémoire ne me trompe complètement (ce qui tout à fait possible, en fait), cela donne une moyenne cas O(n**2) d'exécution.

Answer 4

Si vous êtes prêt à faire l'hypothèse que votre générateur de nombres aléatoires toujours trouver une valeur unique avant de faire du vélo à une valeur vu précédemment pour un tirage donné, cet algorithme est O (m ^ 2), où m est la nombre de valeurs uniques que vous dessinez.

Donc, si vous dessinez des valeurs de m à partir d'un ensemble de valeurs de n, la 1ère valeur vous demandera de dessiner au plus 1 pour obtenir une valeur unique. Le 2 nécessite au plus 2 (vous voyez la 1ère valeur, une valeur unique), 3ème 3, ... MTH m. Par conséquent au total dont vous avez besoin 1 + 2 + 3 + ... + m = [m * (m + 1)] / 2 = (m ^ 2 + m) / 2 nuls. Ceci est O (m ^ 2).

Sans cette hypothèse, je ne sais pas comment vous pouvez même garantir l'algorithme complètera. Il est tout à fait possible (en particulier avec un générateur de nombres pseudo-aléatoires qui peuvent avoir un cycle), que vous garderez voir les mêmes valeurs reprises et jamais à une autre valeur unique.

== == EDIT

Pour le cas moyen:

Sur votre premier tirage, vous ferez exactement 1 match nul. Sur votre 2ème tirage, vous vous attendez à faire 1 (tirage au sort avec succès) + 1 / n (le tirage « partielle » qui représente la chance de dessiner une répétition) Sur votre 3ème tirage au sort, vous vous attendez à faire 1 (le tirage au sort avec succès) + 2 / n (le tirage « partielle » ...) ... Sur votre MTH tirage au sort, vous vous attendez à faire 1 + (m-1) / n dessine.

Ainsi, vous faire 1 + (1 + 1 / n) + (1 + 2 / n) + ... + (1 + (m-1) / n) tire tout à fait dans le cas moyen.

ce qui correspond à la somme de i = 0 à (m-1) [1 + i / n]. Nous allons indiquer que la somme (1 + i / n, i, 0, m-1).

Alors:

sum(1 + i/n, i, 0, m-1) = sum(1, i, 0, m-1) + sum(i/n, i, 0, m-1)
                        = m + sum(i/n, i, 0, m-1)
                        = m + (1/n) * sum(i, i, 0, m-1)
                        = m + (1/n)*[(m-1)*m]/2
                        = (m^2)/(2n) - (m)/(2n) + m 

Nous laissons tomber les termes d'ordre faible et les constantes, et nous obtenons que ce soit O (m ^ 2 / n), où m est le nombre à tirer et n est la taille de la liste.

Answer 5

Il y a un algorithme belle O (n) pour cela. Il se présente comme suit. Supposons que vous avez des articles n, à partir duquel vous souhaitez sélectionner des éléments de m. Je suppose que la fonction rand () donne un nombre réel aléatoire entre 0 et 1. Voici l'algorithme:

items_left=n
items_left_to_pick=m
for j=1,...,n
    if rand()<=(items_left_to_pick/items_left)
        Pick item j
        items_left_to_pick=items_left_to_pick-1
    end
    items_left=items_left-1
end

Il peut être prouvé que cet algorithme ne choisit en effet chaque sous-ensemble d'éléments de m avec une probabilité égale, bien que la preuve est non évidente. Malheureusement, je n'ai pas de référence à portée de main pour le moment.

Modifier L'avantage de cet algorithme est qu'il ne prend que O (m) mémoire (en supposant que les éléments sont simplement des nombres entiers ou peuvent être générés à la volée) par rapport à faire un remaniement, qui prend O (n) de mémoire.

Answer 6

Le pire des cas pour cet algorithme est clairement lorsque vous choisissez l'ensemble des éléments N. Cela équivaut à demander: En moyenne, combien de fois dois-je rouler un dé N-face avant de chaque côté est venu au moins une fois

Réponse: N * H _N , où H _N est le Nième nombre harmonique ,

une valeur approchée par log(N) célèbre.

Cela signifie que l'algorithme en question est N log N.

A titre d'exemple amusant, si vous rouler un dé à 6 faces ordinaire jusqu'à ce que l'un de chaque numéro, il faudra, en moyenne, 6 H ₆ = 14.7 rouleaux.

Answer 7

Avant de pouvoir répondre à cette question dans les détails, permet de définir le cadre. Supposons que vous ayez une collection {a1, a2, ..., un} de n objets distincts, et que vous voulez choisir m des objets distincts de cet ensemble, de telle sorte que la probabilité d'un aj donnée d'un objet apparaissant dans le résultat est le même pour tous les objets .

Si vous avez déjà choisi des éléments de k, et choisissez radomly un élément de l'ensemble {a1, a2, ..., an}, la probabilité que l'élément n'a pas été pris avant est (n-k) / n. Cela signifie que le nombre d'échantillons que vous devez prendre avant d'obtenir un nouvel objet est (en supposant l'indépendance de l'échantillonnage aléatoire) géométrique avec le paramètre (nk) / n. Ainsi, le nombre attendu d'échantillons pour obtenir un élément supplémentaire est n / (n-k), qui est proche de 1 si k est faible par rapport à n.

En conclusion, si vous avez besoin m des objets uniques, choisis au hasard, cet algorithme vous donne

n / n + n / (n-1) + n / (n-2) + n / (n-3) + .... + n / (n (m-1))

qui, comme montré Alderath, peut être estimée par

m * n / (n-m + 1).

Vous pouvez voir un peu plus de cette formule:  * Le nombre attendu d'échantillons pour obtenir une nouvelle augmentation de l'élément unique en tant que nombre d'objets déjà choisi augmente (ce qui semble logique).  * Vous pouvez vous attendre vraiment des temps de calcul lorsque m est proche de n, surtout si n est grand.

Pour obtenir m membres uniques de l'ensemble, utilisez une variante de David algorithme de Knuth pour l'obtention d'une permutation aléatoire. Ici, je suppose que les n objets sont stockés dans un tableau.

for i = 1..m
  k = randInt(i, n)
  exchange(i, k)
end

ici, les échantillons randint un nombre entier de {i, i + 1, ... n}, et l'échange flips deux membres du tableau. Il vous suffit de mélanger m fois, de sorte que le temps de calcul est O (m), alors que la mémoire est O (n) (bien que vous pouvez l'adapter pour enregistrer uniquement les entrées telles que [i] <> i, ce qui donnerait vous O (m) sur le temps et la mémoire, mais avec des constantes plus élevées).

Answer 8

La plupart des gens oublient que regardant, si le nombre a déjà couru, prend également un certain temps.

Le nombre d'essais nessesary peut, descriped plus tôt que, évalué à partir de:

T(n,m) = n(H(n)-H(n-m)) ⪅ n(ln(n)-ln(n-m))

qui va à n*ln(n) pour des valeurs intéressantes de m

Cependant, pour chacun de ces « essais », vous devrez faire une recherche. Cela pourrait être un simple O(n) RUNTHROUGH, ou quelque chose comme un arbre binaire. Cela vous donnera une performance totale de n^2*ln(n) ou n*ln(n)^2.

Pour les plus petites valeurs de m (m < n/2), vous pouvez faire une très bonne approximation pour T(n,m) en utilisant la HA-inéquation, ce qui donne la formule:

2*m*n/(2*n-m+1)

m va à n, cela donne une limite inférieure des essais de performances et O(n) O(n^2) ou O(n*ln(n)).

Tous les résultats sont cependant beaucoup mieux, que je ne l'aurais prévu, ce qui montre que l'algorithme pourrait effectivement être très bien dans de nombreux cas non critiques, où vous pouvez accepter parfois plus temps en cours d'exécution (lorsque vous êtes malchanceux).