Comment trouver la médiane d'un très grand tableau en php

En PHP, nous devons parfois traiter un très grand tableau, comme trouver la médiane. Mais pour les très grandes baies, l’utilisation des méthodes de tri traditionnelles prendra beaucoup de temps et de mémoire. Alors, existe-t-il un moyen plus efficace de trouver la médiane d’un très grand tableau ? Cet article présentera une méthode de solution efficace basée sur l'algorithme de sélection rapide.

1. Introduction à l'algorithme de sélection rapide

L'algorithme de sélection rapide est un algorithme amélioré basé sur l'algorithme de tri rapide. Son idée principale est de trouver le kième plus petit élément dans un tableau non ordonné par division rapide. Sa complexité temporelle est O(n), ce qui est plus efficace que la complexité temporelle de l'algorithme de tri conventionnel O(n log n).

Les étapes de base de l'algorithme de sélection rapide sont les suivantes :

1. Sélectionnez un élément pivot (généralement le premier élément du tableau)
2. Divisez les éléments du tableau en deux parties plus petites que le pivot et plus grandes que ; le pivot ;
3. Si si le nombre d'éléments inférieurs au pivot est inférieur à k, continuez à rechercher le k-ème élément parmi les éléments plus grands que le pivot
4. Si le nombre d'éléments inférieurs au pivot est supérieur ou égal à ; k, continuez à rechercher le k-ème élément parmi les éléments plus petits que l'élément pivot ;
5. Répétez les étapes ci-dessus jusqu'à ce que le k-ème élément soit trouvé.
6. Trouver la médiane d'un très grand tableau

Nous voyons maintenant comment utiliser l'algorithme de sélection rapide pour trouver la médiane d'un très grand tableau. Supposons que nous ayons un très grand tableau $nums$ et que nous devions trouver sa médiane. Nous effectuons d'abord une division rapide sur $nums$, divisant les éléments en deux parties plus petites que le pivot et plus grandes que le pivot. Si le pivot est exactement au milieu du tableau, alors c'est la médiane. Sinon, en fonction de la localisation du pivot, on peut juger que la recherche doit se poursuivre du côté où se trouve le pivot.

Voici les étapes détaillées de l'algorithme :

1. Tout d'abord, nous devons déterminer la position du milieu médian. Si le nombre d'éléments $n$ dans le tableau est un nombre impair, la médiane est $nums[(n-1)/2]$ si le nombre d'éléments $n$ est un nombre pair, la médiane est $( ; nombres[n /2-1]+numéros[n/2])/2$.
2. Divisez rapidement le tableau $nums$ et enregistrez la position du pivot $pos$.
3. En fonction de la relation de position entre pos et mid, déterminez si la médiane est du côté gauche ou droit du pivot. Si $pos< mid$, alors la médiane est entre les positions $[pos+1,n-1]$ si $pos>=mid$, alors la médiane est entre les positions $[0,pos-1]$ ;
4. Répétez les étapes 2 et 3 jusqu'à ce que vous trouviez la médiane.

Ce qui suit est l'implémentation du code PHP correspondant :

function quickSelect($nums, $k) {
    $n = count($nums);
    $left = 0;
    $right = $n - 1;
    $mid = ($n - 1) / 2;

    while (true) {
        $pos = partition($nums, $left, $right);
        if ($pos == $mid) {
            if ($n % 2 == 0) {
                // 偶数个元素
                return ($nums[$pos] + $nums[$pos + 1]) / 2;
            } else {
                // 奇数个元素
                return $nums[$pos];
            }
        } elseif ($pos < $mid) {
            $left = $pos + 1;
        } else {
            $right = $pos - 1;
        }
    }
}

function partition(&$nums, $left, $right) {
    $pivot = $nums[$left];
    $i = $left;
    $j = $right;

    while ($i < $j) {
        while ($i < $j && $nums[$j] >= $pivot) {
            $j--;
        }
        while ($i < $j && $nums[$i] <= $pivot) {
            $i++;
        }
        if ($i < $j) {
            $temp = $nums[$i];
            $nums[$i] = $nums[$j];
            $nums[$j] = $temp;
        }
    }

    // 将pivot元素放到正确的位置
    $nums[$left] = $nums[$i];
    $nums[$i] = $pivot;

    return $i;
}

// 测试示例
$nums = array(1, 2, 3, 4, 5, 6, 7, 8, 9);
echo quickSelect($nums, 5); // 输出5（因为5在数组中的中间位置）

3. Résumé

Pour les très grands tableaux, l'utilisation de méthodes de tri traditionnelles apportera une complexité temporelle et spatiale très élevée. En utilisant l'algorithme de sélection rapide pour trouver le kième plus petit élément, nous pouvons terminer l'opération dans un délai de complexité temporelle O(n), obtenant ainsi une solution efficace à la médiane d'un très grand tableau. Il convient de noter qu'en utilisation réelle, nous devons également effectuer une optimisation appropriée en fonction de différents besoins, comme l'élagage, etc.

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!