PHP 배열 정렬 알고리즘 복잡도: 버블 정렬: O(n^2) 빠른 정렬: O(n log n) (평균) 병합 정렬: O(n log n)
PHP 배열 정렬 알고리즘 복잡도 분석
PHP에는 배열의 요소를 정렬하는 데 사용할 수 있는 여러 정렬 알고리즘이 있습니다. 각 알고리즘의 효율성은 배열의 크기와 데이터의 분포에 따라 다릅니다.
버블 정렬
버블 정렬은 간단한 정렬 알고리즘이지만 효율성이 떨어집니다. 인접한 요소를 반복적으로 비교하고 더 큰 요소를 배열 끝으로 교환하는 방식으로 작동합니다.
function bubbleSort($arr) { for ($i = 0; $i < count($arr); $i++) { for ($j = 0; $j < count($arr) - $i - 1; $j++) { if ($arr[$j] > $arr[$j + 1]) { $temp = $arr[$j]; $arr[$j] = $arr[$j + 1]; $arr[$j + 1] = $temp; } } } return $arr; }
시간 복잡도: O(n^2)
빠른 정렬
빠른 정렬은 분할 정복 알고리즘이며 일반적으로 가장 효율적인 정렬 알고리즘으로 간주됩니다. 재귀를 사용하여 배열을 더 작은 하위 배열로 나누고 각 하위 배열을 정렬합니다.
function quickSort($arr) { if (count($arr) <= 1) { return $arr; } $pivot = $arr[count($arr) - 1]; $left = []; $right = []; for ($i = 0; $i < count($arr) - 1; $i++) { if ($arr[$i] < $pivot) { $left[] = $arr[$i]; } else { $right[] = $arr[$i]; } } return array_merge(quickSort($left), [$pivot], quickSort($right)); }
시간 복잡도: O(n log n)(평균)
Merge sort
Merge sort도 분할 정복 알고리즘입니다. 배열을 더 작은 하위 배열로 재귀적으로 나누고 하위 배열을 정렬한 다음 정렬된 하위 배열을 병합하는 방식으로 작동합니다.
function mergeSort($arr) { if (count($arr) <= 1) { return $arr; } $mid = count($arr) / 2; $left = mergeSort(array_slice($arr, 0, $mid)); $right = mergeSort(array_slice($arr, $mid)); return merge($left, $right); } function merge($left, $right) { $merged = []; $i = $j = 0; while ($i < count($left) && $j < count($right)) { if ($left[$i] <= $right[$j]) { $merged[] = $left[$i]; $i++; } else { $merged[] = $right[$j]; $j++; } } return array_merge($merged, array_slice($left, $i), array_slice($right, $j)); }
시간 복잡도: O(n log n)
실용 사례
10000개의 정수를 포함하는 배열이 있다고 가정합니다. 위의 알고리즘을 사용하여 이 배열을 정렬하고 PHP의 microtime() 함수를 사용하여 정렬하는 데 걸리는 시간을 측정할 수 있습니다.
$arr = range(1, 10000); shuffle($arr); // 打乱数组以获得更现实的结果 $timeStart = microtime(true); bubbleSort($arr); $timeEnd = microtime(true); echo "Bubble Sort: " . ($timeEnd - $timeStart) . " 秒\n"; $timeStart = microtime(true); quickSort($arr); $timeEnd = microtime(true); echo "Quick Sort: " . ($timeEnd - $timeStart) . " 秒\n"; $timeStart = microtime(true); mergeSort($arr); $timeEnd = microtime(true); echo "Merge Sort: " . ($timeEnd - $timeStart) . " 秒\n";
10,000개의 정수 배열에 대한 결과는 다음과 같습니다.
Bubble Sort: 1.0129920272827 秒 Quick Sort: 0.001443982124329 秒 Merge Sort: 0.001151084899902 秒
결과는 빠른 정렬과 병합 정렬이 버블 정렬보다 훨씬 더 효율적이라는 것을 보여줍니다.
위 내용은 다양한 PHP 배열 정렬 알고리즘의 복잡성 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!