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

本文整理 PHP 中常用的演算法實作，並標註其時間複雜度，供開發者參考學習。

時間複雜度階層

常見時間複雜度由低到高排序：

• 常數階 O(1)
• 對數階 O(log₂n)
• 線性階 O(n)
• 線性對數階 O(n log₂n)
• 平方階 O(n²)
• 立方階 O(n³)

演算法實作範例

1. 二分查找 — O(log₂n)

function erfen($a, $l, $h, $f) {
    if ($l > $h) { return false; }
    $m = intval(($l + $h) / 2);
    if ($a[$m] == $f) {
        return $m;
    } elseif ($f < $a[$m]) {
        return erfen($a, $l, $m - 1, $f);
    } else {
        return erfen($a, $m + 1, $h, $f);
    }
}
$a = array(1, 12, 23, 67, 88, 100);
var_dump(erfen($a, 0, 5, 1));

2. 目錄遞迴遍歷 — O(log₂n)

function bianli($p) {
    $a = array();
    foreach (glob($p . '/*') as $f) {
        if (is_dir($f)) {
            $a = array_merge($a, bianli($f));
        } else {
            $a[] = $f;
        }
    }
    return $a;
}

3. 階乘遞迴 — O(log₂n)

function jc($n) {
    if ($n <= 1) { return 1; }
    else { return $n * jc($n - 1); }
}

4. 快速排序 — O(n log₂n)

function kuaisu($a) {
    $c = count($a);
    if ($c <= 1) { return $a; }
    $l = $r = array();
    for ($i = 1; $i < $c; $i++) {
        if ($a[$i] < $a[0]) { $l[] = $a[$i]; }
        else { $r[] = $a[$i]; }
    }
    $l = kuaisu($l);
    $r = kuaisu($r);
    return array_merge($l, array($a[0]), $r);
}

5. 插入排序 — O(n²)

function charu($a) {
    $c = count($a);
    for ($i = 1; $i < $c; $i++) {
        $t = $a[$i];
        for ($j = $i; $j > 0 && $a[$j-1] > $t; $j--) {
            $a[$j] = $a[$j-1];
        }
        $a[$j] = $t;
    }
    return $a;
}

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

function xuanze($a) {
    $c = count($a);
    for ($i = 0; $i < $c; $i++) {
        for ($j = $i+1; $j < $c; $j++) {
            if ($a[$i] > $a[$j]) {
                $t = $a[$j];
                $a[$j] = $a[$i];
                $a[$i] = $t;
            }
        }
    }
    return $a;
}

7. 冒泡排序 — O(n²)

function maopao($a) {
    $c = count($a);
    for ($i = 0; $i < $c; $i++) {
        for ($j = $c-1; $j > $i; $j--) {
            if ($a[$j] < $a[$j-1]) {
                $t = $a[$j-1];
                $a[$j-1] = $a[$j];
                $a[$j] = $t;
            }
        }
    }
    return $a;
}

8. 排列組合（二進制法）

function plzh($arr, $size = 5) {
    $len = count($arr);
    $max = pow(2, $len);
    $min = pow(2, $size) - 1;
    $r_arr = array();
    for ($i = $min; $i < $max; $i++) {
        $count = 0;
        $t_arr = array();
        for ($j = 0; $j < $len; $j++) {
            $a = pow(2, $j);
            $t = $i & $a;
            if ($t == $a) {
                $t_arr[] = $arr[$j];
                $count++;
            }
        }
        if ($count == $size) {
            $r_arr[] = $t_arr;
        }
    }
    return $r_arr;
}
$pl = plzh(array(1,2,3,4,5,6,7), 5);
var_dump($pl);

總結

掌握常見演算法的實作與時間複雜度，有助於在實際專案中選擇最適合的解決方案，提升程式效能。