O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
<?php
function binarySearch(array $arr, int $target): int|false {
$low = 0; $high = count($arr) - 1;
while ($low <= $high) {
$mid = (int)(($low + $high) / 2);
if ($arr[$mid] === $target) return $mid;
if ($arr[$mid] < $target) $low = $mid + 1;
else $high = $mid - 1;
}
return false;
}
// 前提:陣列已排序
$arr = [1, 12, 23, 67, 88, 100];
var_dump(binarySearch($arr, 23)); // int(2)
?>
<?php
function scanTree(string $path): array {
$files = [];
foreach (glob($path . '/*') as $item) {
if (is_dir($item)) {
$files = array_merge($files, scanTree($item));
} else {
$files[] = $item;
}
}
return $files;
}
// 使用 SPL 更高效
$iterator = new RecursiveIteratorIterator(new RecursiveDirectoryIterator($path));
foreach ($iterator as $file) { /* ... */ }
?>
<?php
function factorial(int $n): int {
return $n <= 1 ? 1 : $n * factorial($n - 1);
}
// 尾遞迴優化 (PHP 不支援 TCO,大 n 會堆疊溢位)
function factorialTail(int $n, int $acc = 1): int {
return $n <= 1 ? $acc : factorialTail($n - 1, $n * $acc);
}
// 迴圈版最佳
function factorialIter(int $n): int {
$r = 1; for ($i = 2; $i <= $n; $i++) $r *= $i; return $r;
}
?>
<?php
function quickSort(array $arr): array {
if (count($arr) <= 1) return $arr;
$pivot = $arr[0];
$left = $right = [];
for ($i = 1; $i < count($arr); $i++) {
$arr[$i] < $pivot ? $left[] = $arr[$i] : $right[] = $arr[$i];
}
return array_merge(quickSort($left), [$pivot], quickSort($right));
}
// 原地分區版本可節省記憶體
?>
<?php
function insertionSort(array $arr): array {
for ($i = 1; $i < count($arr); $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
return $arr;
}
?>
<?php
function selectionSort(array $arr): array {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$minIdx = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$j] < $arr[$minIdx]) $minIdx = $j;
}
if ($minIdx !== $i) [$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
}
return $arr;
}
?>
<?php
function bubbleSort(array $arr): array {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = $n - 1; $j > $i; $j--) {
if ($arr[$j] < $arr[$j - 1]) {
[$arr[$j], $arr[$j - 1]] = [$arr[$j - 1], $arr[$j]];
}
}
}
return $arr;
}
?>
<?php
/**
* 從 $arr 中取 $size 個元素的所有組合
* 利用二進位遮罩:n 位元中有 size 位為 1 的所有排列
*/
function combinations(array $arr, int $size): array {
$n = count($arr);
$max = 1 << $n; // 2^n
$min = (1 << $size) - 1; // 最小含 size 個 1 的數
$result = [];
for ($mask = $min; $mask < $max; $mask++) {
// 計算 1 的個數 (Brian Kernighan 算法)
$cnt = 0;
for ($m = $mask; $m; $m &= $m - 1) $cnt++;
if ($cnt !== $size) continue;
$comb = [];
for ($j = 0; $j < $n; $j++) {
if ($mask & (1 << $j)) $comb[] = $arr[$j];
}
$result[] = $comb;
}
return $result;
}
// 範例:5 選 3
print_r(combinations([1,2,3,4,5], 3));
/*
Array(
[0]=>Array(1,2,3) [1]=>Array(1,2,4) [2]=>Array(1,2,5)
[3]=>Array(1,3,4) [4]=>Array(1,3,5) [5]=>Array(1,4,5)
[6]=>Array(2,3,4) [7]=>Array(2,3,5) [8]=>Array(2,4,5)
[9]=>Array(3,4,5)
)
*/
?>
sort() (快速排序)、usort()、ksort() 等 C 實作,遠快於使用者空間排序。array_search(), in_array() (O(n)),大量查找改用 isset($map[$key]) (O(1))。array_unique()。itertools 風格生成器避免一次產生巨大陣列。| 演算法 | 最佳 | 平均 | 最差 | 空間 | 穩定 |
|---|---|---|---|---|---|
| 二分搜尋 | O(1) | O(log n) | O(log n) | O(1) | - |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 |
| 合併排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 選擇排序 | O(n²) | O(n²) | O(n²) | O(1) | 否 |
| 氣泡排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |