萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 常見演算法實作與時間複雜度分析

時間複雜度階層

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

1. 二分搜尋 - O(log 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)
?>

2. 遞迴遍歷目錄樹 - O(n) (n=檔案總數)

<?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) { /* ... */ }
?>

3. 遞迴階乘 - O(n)

<?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;
}
?>

4. 快速排序 - 平均 O(n log n)

<?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));
}
// 原地分區版本可節省記憶體
?>

5. 插入排序 - O(n²) (小資料/近乎有序時快)

<?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;
}
?>

6. 選擇排序 - O(n²)

<?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;
}
?>

7. 氣泡排序 - O(n²) (教學用,實務不用)

<?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;
}
?>

8. 組合生成 (位元遮罩法) - O(2ⁿ)

<?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)
)
*/
?>

PHP 內建函式優先原則

  • 排序: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)是
copyright © 萬盛學電腦網 all rights reserved