当前位置：首页 > news >正文

PHP算法复杂度与性能预估

news 2026/6/13 17:22:02

PHP算法复杂度与性能预估

算法复杂度分析是计算机科学的基础。虽然PHP是高级语言，但理解复杂度对写高效代码有帮助。今天说说PHP中的算法复杂度。

时间复杂度表示算法运行时间随数据量的增长关系。

```php
// O(1) - 常数时间
function getFirst(array $arr): mixed
{
return $arr[0];
}

// O(n) - 线性时间
function sum(array $arr): float
{
$sum = 0;
foreach ($arr as $v) $sum += $v;
return $sum;
}

// O(n²) - 平方时间
function bubbleSort(array $arr): array
{
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
[$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
}
}
}
return $arr;
}

// O(log n) - 对数时间
function binarySearch(array $arr, int $target): int
{
$left = 0;
$right = count($arr) - 1;
while ($left <= $right) {
$mid = $left + intdiv($right - $left, 2);
if ($arr[$mid] === $target) return $mid;
if ($arr[$mid] < $target) $left = $mid + 1;
else $right = $mid - 1;
}
return -1;
}
?>

不同数据量下各种操作的时间对比。

```php
function benchmarkComplexity(): void
{
$sizes = [100, 1000, 10000];

foreach ($sizes as $size) {
echo "\n数据量: $size\n";
$data = range(1, $size);

// array_key_exists O(1)
$start = microtime(true);
for ($i = 0; $i < 1000; $i++) array_key_exists($size - 1, $data);
echo " key_exists: " . round((microtime(true) - $start) * 1000, 2) . "ms\n";

// in_array O(n)
$start = microtime(true);
for ($i = 0; $i < 1000; $i++) in_array($size, $data);
echo " in_array: " . round((microtime(true) - $start) * 1000, 2) . "ms\n";

// sort O(n log n)
$copy = $data;
$start = microtime(true);
sort($copy);
echo " sort: " . round((microtime(true) - $start) * 1000, 2) . "ms\n";
}
}

benchmarkComplexity();
?>

空间复杂度表示算法占用的内存。

```php
function linearSpace(int $n): array
{
$result = [];
for ($i = 0; $i < $n; $i++) $result[] = $i;
return $result;
}

function constantSpace(int $n): int
{
$sum = 0;
for ($i = 0; $i < $n; $i++) $sum += $i;
return $sum;
}
?>

常见数据结构的时间复杂度。

// 数组
// 查找: O(1) (key_exists) / O(n) (in_array)
// 插入末尾: O(1)
// 插入开头: O(n)

// 链表
// 查找: O(n)
// 插入: O(1)

// 二叉搜索树
// 查找: O(log n)
// 插入: O(log n)
// 删除: O(log n)

算法复杂度分析帮助预估代码的数据量。选择合适的数据结构和算法，可以在数据量增长时保持性能。PHP内置的sort、array_key_expsts等函数性能很好，尽量用内置函数而不是手写。