PHP에서 계산 정렬 알고리즘의 원리와 시간 복잡도 분석을 알아봅니다.

PHP에서 카운팅 정렬 알고리즘의 원리와 시간 복잡도 분석을 알아보세요

카운팅 정렬은 비비교 정렬 알고리즘으로, 데이터 범위가 작고 알려진 상황에 적합합니다. 기본 아이디어는 정렬을 달성하기 위해 각 요소의 발생 횟수를 계산한 다음 이를 출력 배열에 채우는 것입니다. 이 기사에서는 계산 정렬의 원리, 단계 및 시간 복잡도 분석을 소개하고 특정 PHP 코드 예제를 제공합니다.

1. 원리:
   계산 정렬의 원리는 비교적 간단합니다. 정렬할 배열이 배열이고 요소 범위가 [0, k]라고 가정하면 먼저 각 요소의 발생 횟수를 계산하기 위해 k+1 크기의 계산 배열 count를 만들어야 합니다. 원래 배열을 반복하는 동안 요소의 개수가 계산되어 개수 배열에 저장됩니다. 그런 다음, count 배열의 요소를 순차적으로 누적하여 출력 배열의 요소 위치를 결정합니다. 마지막으로 원래 배열 배열을 순회하고 각 요소를 해당 위치(카운트 인덱스에 따라)에 배치하여 정렬을 완료합니다.
2. 단계:
3. k+1 크기의 카운트 배열 개수를 만들고 0으로 초기화합니다.
4. 원래 배열 배열을 순회하면서 각 요소의 발생 횟수를 세어 count 배열에 저장합니다.
5. 카운트 배열을 누적하여 출력 배열의 각 요소 위치를 결정합니다.
6. 원본 배열과 동일한 크기의 출력 배열 출력을 만듭니다.
7. 원래 배열 배열을 다시 탐색하고 카운트 배열의 인덱스에 따라 각 요소를 출력 배열에 배치합니다.
8. 출력 배열 출력은 계수 정렬 후의 결과입니다.
9. 시간 복잡도 분석:
10. 카운트 배열 생성의 시간 복잡도는 O(k)입니다.
11. 원래 배열을 순회하고 각 요소의 발생 횟수를 세는 시간 복잡도는 O(n)입니다.
12. 카운트 배열을 누적하는 시간 복잡도는 O(k)입니다.
13. 출력 배열을 생성하는 시간 복잡도는 O(n)입니다.
14. 원래 배열을 다시 순회하고 요소를 출력 배열에 배치하는 시간 복잡도는 O(n)입니다.
15. 총 시간 복잡도는 O(k) + O(n) + O(k) + O(n) + O(n)이며 이는 O(n + k)로 단순화됩니다.

다음은 PHP 언어를 사용하여 계수 정렬 알고리즘을 구현한 코드 예제입니다.

function countingSort($array)
{
    $maxValue = max($array);
    $count = array_fill(0, $maxValue + 1, 0);
    $n = count($array);

    foreach ($array as $value) {
        $count[$value]++;
    }

    for ($i = 1; $i <= $maxValue; $i++) {
        $count[$i] += $count[$i - 1];
    }

    $output = array_fill(0, $n, 0);

    for ($i = $n - 1; $i >= 0; $i--) {
        $output[$count[$array[$i]] - 1] = $array[$i];
        $count[$array[$i]]--;
    }

    return $output;
}

$array = [4, 2, 0, 1, 3, 2, 1]; // 待排序数组
$sortedArray = countingSort($array);
print_r($sortedArray);

위는 PHP에서 계수 정렬 알고리즘의 원리와 시간 복잡도 분석을 학습하는 내용입니다. 이것이 계산 정렬을 이해하는 데 도움이 되기를 바랍니다.

위 내용은 PHP에서 계산 정렬 알고리즘의 원리와 시간 복잡도 분석을 알아봅니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!