Comment le Fisher-Yates Shuffle peut-il réaliser un brassage aléatoire en temps linéaire ?

Algorithme de brassage Fisher-Yates : un algorithme de brassage temporel linéaire

L'efficacité est cruciale lors du tri aléatoire d'une liste d'entiers. Bien que la méthode originale de la question tente d'obtenir le caractère aléatoire, elle peut rencontrer des problèmes d'efficacité pendant le traitement, en particulier vers la fin.

Une solution plus efficace est l'algorithme de lecture aléatoire de Fisher-Yates, un algorithme en temps linéaire qui garantit une réorganisation véritablement aléatoire de la liste d'entrée. Contrairement à l'approche originale, qui reposait sur un tableau booléen pour suivre les éléments échangés, l'algorithme de lecture aléatoire de Fisher-Yates adopte une approche plus simple.

<code class="language-c#">for (int i = iItemCount - 1; i >= 1; i--)
{
    int j = random.Next(i + 1);
    int temp = values[j];
    values[j] = values[i];
    values[i] = temp;
}</code>

L'algorithme fonctionne en échangeant à plusieurs reprises l'élément actuel avec un élément précédemment sélectionné au hasard dans la liste. Au fur et à mesure que l'algorithme progresse, il réduit la gamme d'éléments non triés, mélangeant ainsi la liste entière en un temps O(n).

En utilisant l'algorithme de brassage de Fisher-Yates, vous pouvez réorganiser efficacement et aléatoirement une liste d'entiers, évitant ainsi les pièges potentiels de l'algorithme d'origine.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!