Quelle est la valeur o pour la sélection aléatoire naïve de l'ensemble fini?

Il y a un bel algorithme O (n) pour cela. Cela va comme suit. Dites que vous avez n articles, à partir desquels vous voulez choisir M Articles. 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

Si vous êtes prêt à supposer que votre générateur de nombres aléatoires trouvera toujours une valeur unique avant de revenir à une valeur de cyclage à une valeur précédemment vue pour un tirage donné, cet algorithme est O (m ^ 2), où M est le Nombre de valeurs uniques que vous dessinez.

Donc, si vous dessinez des valeurs M à partir d'un ensemble de n valeurs N, la 1ère valeur nécessitera de dessiner au plus 1 pour obtenir une valeur unique. Le 2e requiert au plus 2 (vous voyez la 1ère valeur, puis une valeur unique), le 3ème 3, ... le MTH m. Par conséquent, vous avez besoin de 1 + 2 + 3 + ... + m = [m * (m + 1)] / 2 = (m ^ 2 + m) / 2 tirages. C'est O (m ^ 2). P>

Sans cette hypothèse, je ne sais pas comment vous pouvez même garantir l'algorithme terminer. C'est tout à fait possible (surtout avec un générateur de nombres pseudo-aléatoires pouvant avoir un cycle), que vous continuerez à voir les mêmes valeurs encore et encore et que vous n'allez jamais à une autre valeur unique. p>

== Edit == p>

pour le cas moyen: p>

sur votre premier tirage, vous ferez exactement 1 tirage au sort. Sur votre 2e tirage, vous vous attendez à faire 1 (le tirage au sort fructueux) + 1 / N (le dessin "partiel" qui représente vos chances de dessiner une répétition) Sur votre 3ème dessin, vous vous attendez à faire 1 (le tirage réussi) + 2 / N (le dessin "partiel" ...) ... Sur votre mth dessin, vous vous attendez à faire des dessins de 1 + (m-1) / n. P>

Ainsi, vous ferez 1 + (1 + 1 / N) + (1 + 2 / N) + (1 + 2 / N) + ... + (1 + (m-1) / n) attire tout à fait dans le boîtier moyen. P>

Ceci est égal à la somme de i = 0 à (m-1) de [1 + i / n ]. Notons cette somme (1 + I / N, I, 0, M-1). P>

ALORS: P>

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 

Si vous avez déjà choisi I valeurs I, la probabilité que vous choisissez une nouvelle à partir d'un ensemble de valeurs Y est

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

Variables

n = la quantité totale d'éléments dans l'ensemble
m = la quantité de valeurs uniques à extraire de l'ensemble des éléments N
d (i) = la quantité attendue des essais nécessaires pour atteindre une valeur à l'étape i
i = dénote une étape spécifique. I ∈ [0, N-1]
t (m, n) = montant total attendu d'essais pour la sélection d'éléments uniques à partir d'un ensemble d'éléments N à l'aide de l'algorithme naïf

raisonnement

La première étape, i = 0, est triviale. Peu importe la valeur que nous choisissons, nous en avons 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 (l'essai où nous choisissons une valeur unique valide). En plus de cela, il y a une chance que nous choisissions la mauvaise valeur. Cette chance est (quantité d'éléments préalablement choisis) / (quantité totale d'éléments). Dans ce cas 1 / N. Dans le cas où nous avons choisi le mauvais article, il y a une chance de 1 / n que nous puissions choisir le mauvais article. Multiplier ceci par 1 / N, car c'est la probabilité combinée que nous choisissons de mauvais moments, donne (1 / N) ^{2 . Pour comprendre cela, il est utile de dessiner un Arbre de décision . Après avoir choisi un article non unique deux fois, il y a une probabilité que nous le ferons à nouveau. Cela se traduit par l'ajout de (1 / N) 3 au total des quantités attendues d'essais à l'étape i = 1. Chaque fois que nous choisissons le mauvais numéro, il y a une chance que nous puissions choisir le mauvais numéro. Il en résulte:}

D (1) = 1 + 1 / N + (1 / N) 2 + (1 / N) 3 + (1 / N) 4 + ...

De même, dans le général I: Th Step, la chance de choisir le mauvais article dans un seul choix est I / N, ce qui compte:

d (i) = 1 + i / n + (i / n) 2 + (i / n) 3 + (i / n) 4 + ... =
= somme ((i / n) k ), où k ∈ [0, ∞]

Ceci est un séquence géométrique et il est donc facile de calculer sa somme:

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

La complexité globale est ensuite calculée en additionnant la quantité attendue des essais à chaque étape:

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

Extension des fractions dans 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)

Nous pouvons utiliser le fait que:

N / N ≤ N / (N-1) ≤ N / (N-2) ≤ N / (N-3) ≤ ... ≤ N / (N-M + 2) ≤ N / (N- m + 1)

Puisque 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)

Cela pourrait être (et probablement) possible d'établir une limite supérieure légèrement plus stricte en utilisant une technique pour évaluer la série au lieu de la bornisation par la méthode approximative de (quantité de termes) * (terme plus élevé)

Conclusion

Cela signifierait que la commande Big-o est o (m * n / (n-m + 1)) . Je ne vois aucun moyen possible de simplifier cette expression de la façon dont c'est.

Retour en arrière à la suite de Vérifiez si cela a du sens , nous voyons que, si N est constant, et m est plus proche et plus proche de N, les résultats augmenteront rapidement, car le dénominateur augmente, car le dénominateur devient rapidement. très petit. C'est ce que nous attendions, si nous considérons par exemple l'exemple donné dans la question de la sélection de «999 999 valeurs d'un ensemble de 1 000 000». Si nous, que nous soyons constants et n grandir vraiment, vraiment grand, la complexité convergera vers O (m) dans la limite n → ∞. C'est aussi ce que nous attendions, car tout en choisissant un nombre constant d'éléments d'une taille "proche de" de taille infini, la probabilité de choisir une valeur précédemment choisie est essentiellement 0. I.e. Nous avons besoin de m essais indépendamment de n car il n'y a pas de collision.