PHP에서 매우 큰 배열의 중앙값을 찾는 방법

PHP에서는 중앙값을 구하는 등 매우 큰 배열을 처리해야 하는 경우가 있습니다. 그러나 매우 큰 배열의 경우 기존 정렬 방법을 사용하면 시간과 메모리가 많이 소모됩니다. 그렇다면 매우 큰 배열의 중앙값을 찾는 더 효율적인 방법이 있습니까? 이 글에서는 빠른 선택 알고리즘을 기반으로 한 효율적인 해결 방법을 소개합니다.

1. 빠른 선택 알고리즘 소개

빠른 선택 알고리즘은 빠른 정렬 알고리즘을 기반으로 개선된 알고리즘으로, 빠른 분할을 통해 순서가 지정되지 않은 배열에서 k번째로 작은 요소를 찾는 것입니다. 시간 복잡도는 O(n)으로 기존 정렬 알고리즘의 시간 복잡도 O(n log n)보다 효율적입니다.

빠른 선택 알고리즘의 기본 단계는 다음과 같습니다.

1. 피벗 요소 피벗(일반적으로 배열의 첫 번째 요소)을 선택합니다.
2. 배열의 요소를 피벗보다 작은 부분과 큰 부분으로 나눕니다.
3. 피벗보다 작은 요소의 수가 k보다 작으면 피벗보다 큰 요소 중에서 k번째 요소를 계속 검색합니다.
4. 피벗보다 작은 요소의 수가 다음보다 크거나 같으면; k, 피벗 요소보다 작은 요소 중에서 k번째 요소를 계속해서 찾습니다.
5. k번째 요소를 찾을 때까지 위 단계를 반복합니다.
6. 매우 큰 배열의 중앙값 찾기

이제 빠른 선택 알고리즘을 사용하여 매우 큰 배열의 중앙값을 찾는 방법을 고려합니다. 매우 큰 배열 $nums$이 있고 중앙값을 찾아야 한다고 가정해 보겠습니다. 먼저 $nums$에 대해 빠른 분할을 수행하여 요소를 피벗보다 작고 피벗보다 큰 두 부분으로 나눕니다. 피벗이 정확히 배열의 중앙에 있으면 중앙값입니다. 그렇지 않으면 피벗 위치에 따라 피벗이 있는 쪽에서 검색을 계속해야 한다고 판단할 수 있습니다.

자세한 알고리즘 단계는 다음과 같습니다.

1. 먼저 중앙값 중앙의 위치를 ​​결정해야 합니다. 배열의 $n$ 요소 수가 홀수인 경우 중앙값은 $nums[(n-1)/2]$입니다. $n$ 요소 수가 짝수인 경우 중앙값은 $( 숫자[n /2-1]+숫자[n/2])/2$.
2. 배열 $nums$를 빠르게 나누고 피벗 위치 $pos$를 기록합니다.
3. pos와 mid의 위치 관계를 바탕으로 중앙값이 피봇의 왼쪽에 있는지 오른쪽에 있는지 판단하세요. $pos< mid$인 경우 중앙값은 위치 $[pos+1,n-1]$ 사이에 있고, $pos>=mid$인 경우 중앙값은 위치 $[0,pos-1]$ 사이에 있습니다.
4. 중앙값을 찾을 때까지 2단계와 3단계를 반복하세요.

다음은 해당 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!