
Envoyé par
millie
Si on veut faire un tableau de n nombres sans doublons.
Si on en a déjà tiré p. Le probabilité d'en tirer un que l'on a déjà pris est donc de : p/n.
Ce qui fait que pour 1000 nombres dans le tableau, si on en a déjà tiré 999, il faudra en temps moyen réaliser 1000 tours de boucle pour prendre celui qu'on a déjà pris...
Le temps moyen est de : Sum(p, p=1 à n) = O(n²).
Dans le pire ces cas, c'est un temps infini (si on tombe toujours sur un nombre déjà tiré). [edit : quasiment infini, la probabilité de tirait 100^100 fois le même nombre de suite est non nulle, pour être plus précis, c'est un algorithme probabiliste de type las vegas, sa terminaison étant presque sûre]
Partager