PHPで非常に大きな配列の中央値を見つける方法

PHP では、中央値を求めるなど、非常に大きな配列を処理する必要がある場合があります。ただし、非常に大きな配列の場合、従来の並べ替え方法を使用すると、非常に時間とメモリを消費します。では、非常に大きな配列の中央値を見つけるより効率的な方法はあるのでしょうか?この記事では、高速選択アルゴリズムに基づいた効率的な解決方法を紹介します。

1. クイック選択アルゴリズムの概要

クイック選択アルゴリズムは、クイック ソート アルゴリズムに基づいて改良されたアルゴリズムです。その主なアイデアは、順序付けされていない配列内の項目を次の方法で検索することです。急速除算 k 番目に小さい要素。その時間計算量は O(n) であり、従来の並べ替えアルゴリズムの時間計算量 O(n log n) よりも効率的です。

クイック選択アルゴリズムの基本的な手順は次のとおりです:

1. ピボット要素 pivot (通常は配列の最初の要素) を選択します。配列内の要素 要素は 2 つの部分に分割されます: pivot より小さい部分と pivot より大きい部分;
2. pivot より小さい要素の数が k 未満の場合は、要素の中から k 番目の要素を検索し続けます。ピボットより大きい;
3. If より小さい場合 ピボット要素の数が k 以上の場合、ピボットより小さい要素の中から k 番目の要素を検索し続けます;
4. 繰り返しk 番目の要素が見つかるまで上記の手順を繰り返します。
5. 非常に大きな配列の中央値を見つける
6. 次に、高速選択アルゴリズムを使用して非常に大きな配列の中央値を見つける方法を検討します。非常に大きな配列 $nums$ があり、その中央値を見つける必要があるとします。まず、$nums$ に対して簡単な除算を実行し、要素をピボットより小さい部分とピボットより大きい 2 つの部分に分割します。ピボットが配列のちょうど中央にある場合、それは中央値です。それ以外の場合は、ピボットの位置に基づいて、ピボットが配置されている側で検索を続行する必要があると判断できます。

以下はアルゴリズムの詳細な手順です:

まず、中央値の中央値の位置を決定する必要があります。配列内の要素 $n$ の数が奇数の場合、中央値は $nums[(n-1)/2]$ になります。要素の数 $n$ が偶数の場合、中央値は $( nums[n /2-1] nums[n/2])/2$。

1. 配列 $nums$ をすばやく分割し、ピボット位置 $pos$ を記録します。
2. posとmidの位置関係に基づいて、中央値がピボットの左側にあるのか右側にあるのかを判断します。 $pos
3. 中央値が見つかるまで手順 2 と 3 を繰り返します。
4. 以下は、対応する PHP コード実装です:

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. 非常に大きな配列の場合、従来の並べ替え方法を使用すると、非常に高度な時間と空間の複雑さ。高速選択アルゴリズムを使用して k 番目に小さい要素を見つけることにより、O(n) 時間の計算量内で演算を完了でき、それによって非常に大きな配列の中央値に対する効率的な解を得ることができます。実際の使用においては、枝刈りなどのさまざまなニーズに応じて適切な最適化を行う必要もあります。

以上がPHPで非常に大きな配列の中央値を見つける方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。