时间复杂度、空间复杂度
计算机科学中的“复杂度”（Complexity）主要指时间复杂度和空间复杂度。
它们都用大
一、 常见时间复杂度(Time Complexity) (从高效到低效)
时间复杂度
| 复杂度类别 | 表示法 | 名称 | 描述 | 示例算法 |
|---|---|---|---|---|
| 常数时间 | Constant Time | 无论输入规模 |
访问数组中的一个元素、简单的加减运算。 | |
| 对数时间 | Logarithmic Time | 每次操作能将问题规模减半。 | 二分搜索、平衡二叉树的查找。 | |
| 线性时间 | Linear Time | 执行时间与输入规模 |
遍历数组、查找未排序数组中的最大值。 | |
| 线性对数时间 | Log-Linear Time | 比线性时间稍慢，但仍是高效的排序算法的基准。 | 归并排序（Merge Sort）、快速排序（Quick Sort）。 | |
| 多项式时间 | Polynomial Time | 冒泡排序 ( |
||
| 指数时间 | Exponential Time | 执行时间随 |
解决旅行推销员问题（暴力法）、斐波那契数列（递归的简单实现）。 | |
| 阶乘时间 | Factorial Time | 随 |
生成一个集合的所有排列。 | |
| 趋势对比图 (直观感受): |
n = 10:
O(1): 1
O(log n): ~3
O(n): 10
O(n log n): ~30
O(n²): 100
O(2ⁿ): 1024
O(n!): 3,628,800
二、 空间复杂度类型 (Space Complexity)(从高效到低效)
空间复杂度
注意: 递归算法的空间复杂度与递归调用栈的最大深度直接相关。
| 复杂度 | 名称 | 描述 | 示例算法 |
|---|---|---|---|
| O(1) | 常数空间 | 最优。算法只使用固定数量的变量，空间不随 n 变化。 |
选择排序、插入排序、冒泡排序（原地排序）。 |
| O(log n) | 对数空间 | 非常高效。通常由递归深度引起。 | 快速排序（递归调用栈的最佳/平均情况）、二分查找的递归实现。 |
| O(n) | 线性空间 | 常见。所需额外空间与 n 成正比。 |
归并排序（需要临时数组）、哈希表（最坏情况）、许多动态规划问题。 |
| O(n²) | 平方空间 | 占用空间大。通常需要二维数组来存储所有配对关系。 | 邻接矩阵表示图、动态规划中的二维 DP 表。 |
额外说明
在分析算法时，通常还会区分三种情况：
- 最好时间复杂度 (Best-Case)：算法在最理想输入下的运行时间。
- 最坏时间复杂度 (Worst-Case)：算法在最差输入下的运行时间（这是我们最常关注和使用的）。
- 平均时间复杂度 (Average-Case)：算法在所有可能的输入下的平均运行时间。
算法复杂度详解
时间复杂度PHP实例
1.1 O(1) - 常数时间
// 访问数组元素
function accessArrayElement($arr, $index) {
return $arr[$index]; // O(1)
}
// 哈希表查找
function hashLookup($hashMap, $key) {
return isset($hashMap[$key]) ? $hashMap[$key] : null; // O(1)
}
// 数学运算
function basicOperations($a, $b) {
$sum = $a + $b; // O(1)
$product = $a * $b; // O(1)
return [$sum, $product];
}
// 测试O(1)
$arr = [1, 2, 3, 4, 5];
echo accessArrayElement($arr, 2); // 输出: 3
1.2 O(log n) - 对数时间
// 二分查找
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr) - 1;
while ($left <= $right) { // O(log n)
$mid = (int)(($left + $right) / 2);
if ($arr[$mid] === $target) {
return $mid;
} elseif ($arr[$mid] < $target) {
$left = $mid + 1;
} else {
$right = $mid - 1;
}
}
return -1;
}
// 测试二分查找
$sortedArr = [1, 3, 5, 7, 9, 11, 13, 15];
echo binarySearch($sortedArr, 9); // 输出: 4
1.3 O(n) - 线性时间
// 遍历数组
function traverseArray($arr) {
$sum = 0;
foreach ($arr as $value) { // O(n)
$sum += $value;
echo $value . " ";
}
return $sum;
}
// 查找未排序数组中的最大值
function findMax($arr) {
if (empty($arr)) return null;
$max = $arr[0];
for ($i = 1; $i < count($arr); $i++) { // O(n)
if ($arr[$i] > $max) {
$max = $arr[$i];
}
}
return $max;
}
// 测试O(n)
$numbers = [3, 1, 4, 1, 5, 9, 2, 6];
echo "数组遍历: " . traverseArray($numbers) . "\n";
echo "最大值: " . findMax($numbers) . "\n";
1.4 O(n log n) - 线性对数时间
// 归并排序
function mergeSort($arr) {
$length = count($arr);
if ($length <= 1) {
return $arr;
}
$mid = (int)($length / 2);
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid);
$left = mergeSort($left); // O(log n) 递归深度
$right = mergeSort($right); // O(log n) 递归深度
return merge($left, $right); // O(n) 合并操作
}
function merge($left, $right) {
$result = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] <= $right[$j]) {
$result[] = $left[$i++];
} else {
$result[] = $right[$j++];
}
}
// 合并剩余元素
while ($i < count($left)) {
$result[] = $left[$i++];
}
while ($j < count($right)) {
$result[] = $right[$j++];
}
return $result;
}
// 快速排序
function quickSort($arr) {
if (count($arr) <= 1) {
return $arr;
}
$pivot = $arr[0];
$left = $middle = $right = [];
foreach ($arr as $value) { // O(n)
if ($value < $pivot) {
$left[] = $value;
} elseif ($value == $pivot) {
$middle[] = $value;
} else {
$right[] = $value;
}
}
return array_merge(
quickSort($left), // O(log n) 递归深度
$middle,
quickSort($right) // O(log n) 递归深度
);
}
// 测试O(n log n)
$unsorted = [38, 27, 43, 3, 9, 82, 10];
echo "归并排序: " . implode(", ", mergeSort($unsorted)) . "\n";
echo "快速排序: " . implode(", ", quickSort($unsorted)) . "\n";
1.5 O(n²) - 平方时间
// 冒泡排序
function bubbleSort($arr) {
$n = count($arr);
for ($i = 0; $i < $n; $i++) { // O(n)
for ($j = 0; $j < $n - $i - 1; $j++) { // O(n)
if ($arr[$j] > $arr[$j + 1]) {
// 交换元素
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
return $arr;
}
// 选择排序
function selectionSort($arr) {
$n = count($arr);
for ($i = 0; $i < $n; $i++) { // O(n)
$minIndex = $i;
for ($j = $i + 1; $j < $n; $j++) { // O(n)
if ($arr[$j] < $arr[$minIndex]) {
$minIndex = $j;
}
}
// 交换元素
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
return $arr;
}
// 测试O(n²)
$numbers = [64, 34, 25, 12, 22, 11, 90];
echo "冒泡排序: " . implode(", ", bubbleSort($numbers)) . "\n";
echo "选择排序: " . implode(", ", selectionSort($numbers)) . "\n";
1.6 O(2ⁿ) - 指数时间
// 斐波那契数列 (朴素递归)
function fibonacci($n) {
if ($n <= 1) {
return $n;
}
return fibonacci($n - 1) + fibonacci($n - 2); // O(2ⁿ)
}
// 子集生成
function generateSubsets($nums) {
$result = [];
$n = count($nums);
$total = 1 << $n; // 2ⁿ
for ($i = 0; $i < $total; $i++) { // O(2ⁿ)
$subset = [];
for ($j = 0; $j < $n; $j++) {
if ($i & (1 << $j)) {
$subset[] = $nums[$j];
}
}
$result[] = $subset;
}
return $result;
}
// 测试O(2ⁿ)
echo "斐波那契(10): " . fibonacci(10) . "\n";
$subsets = generateSubsets([1, 2, 3]);
echo "子集数量: " . count($subsets) . "\n"; // 输出: 8
1.7 O(n!) - 阶乘时间
// 全排列生成
function generatePermutations($nums) {
$result = [];
backtrack($nums, 0, $result);
return $result;
}
function backtrack(&$nums, $start, &$result) {
if ($start == count($nums)) {
$result[] = $nums; // 复制当前排列
return;
}
for ($i = $start; $i < count($nums); $i++) {
// 交换元素
swap($nums, $start, $i);
backtrack($nums, $start + 1, $result);
// 回溯
swap($nums, $start, $i);
}
}
function swap(&$nums, $i, $j) {
$temp = $nums[$i];
$nums[$i] = $nums[$j];
$nums[$j] = $temp;
}
// 测试O(n!)
$permutations = generatePermutations([1, 2, 3]);
echo "排列数量: " . count($permutations) . "\n"; // 输出: 6
foreach ($permutations as $perm) {
echo implode(", ", $perm) . "\n";
}
空间复杂度PHP实例
2.1 O(1) - 常数空间
// 选择排序 (原地排序)
function selectionSortInPlace(&$arr) {
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
$minIndex = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$j] < $arr[$minIndex]) {
$minIndex = $j;
}
}
// 只使用固定数量的临时变量
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
}
// 斐波那契 (迭代版)
function fibonacciIterative($n) {
if ($n <= 1) {
return $n;
}
$a = 0;
$b = 1;
for ($i = 2; $i <= $n; $i++) {
$temp = $a + $b;
$a = $b;
$b = $temp;
}
return $b;
}
// 测试O(1)空间
$arr = [64, 25, 12, 22, 11];
selectionSortInPlace($arr);
echo "排序后: " . implode(", ", $arr) . "\n";
echo "斐波那契(10): " . fibonacciIterative(10) . "\n";
2.2 O(log n) - 对数空间
// 二分查找 (递归版)
function binarySearchRecursive($arr, $target, $left, $right) {
if ($left > $right) {
return -1;
}
$mid = (int)(($left + $right) / 2);
if ($arr[$mid] === $target) {
return $mid;
} elseif ($arr[$mid] < $target) {
return binarySearchRecursive($arr, $target, $mid + 1, $right);
} else {
return binarySearchRecursive($arr, $target, $left, $mid - 1);
}
}
// 测试O(log n)空间
$sortedArr = [1, 3, 5, 7, 9, 11, 13, 15];
$result = binarySearchRecursive($sortedArr, 9, 0, count($sortedArr) - 1);
echo "二分查找结果: " . $result . "\n";
2.3 O(n) - 线性空间
// 归并排序 (需要额外空间)
function mergeSortWithSpace($arr) {
$length = count($arr);
if ($length <= 1) {
return $arr;
}
$mid = (int)($length / 2);
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid);
$left = mergeSortWithSpace($left);
$right = mergeSortWithSpace($right);
return mergeArrays($left, $right); // 需要O(n)额外空间
}
function mergeArrays($left, $right) {
$result = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] <= $right[$j]) {
$result[] = $left[$i++];
} else {
$result[] = $right[$j++];
}
}
// 添加剩余元素
while ($i < count($left)) {
$result[] = $left[$i++];
}
while ($j < count($right)) {
$result[] = $right[$j++];
}
return $result;
}
// 哈希表使用
function countFrequency($arr) {
$frequency = [];
foreach ($arr as $value) {
if (!isset($frequency[$value])) {
$frequency[$value] = 0;
}
$frequency[$value]++;
}
return $frequency; // O(n)空间
}
// 测试O(n)空间
$numbers = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4];
$sorted = mergeSortWithSpace($numbers);
$freq = countFrequency($numbers);
echo "排序后: " . implode(", ", $sorted) . "\n";
echo "频率统计: " . json_encode($freq) . "\n";
2.4 O(n²) - 平方空间
// 邻接矩阵表示图
function createAdjacencyMatrix($n, $edges) {
$matrix = array_fill(0, $n, array_fill(0, $n, 0)); // O(n²)空间
foreach ($edges as $edge) {
$u = $edge[0];
$v = $edge[1];
$weight = $edge[2] ?? 1;
$matrix[$u][$v] = $weight;
$matrix[$v][$u] = $weight; // 无向图
}
return $matrix;
}
// 动态规划 - 最长公共子序列
function longestCommonSubsequence($text1, $text2) {
$m = strlen($text1);
$n = strlen($text2);
// 创建DP表 O(n²)空间
$dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
for ($i = 1; $i <= $m; $i++) {
for ($j = 1; $j <= $n; $j++) {
if ($text1[$i - 1] == $text2[$j - 1]) {
$dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
} else {
$dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
}
}
}
return $dp[$m][$n];
}
// 测试O(n²)空间
$edges = [
[0, 1, 2],
[1, 2, 3],
[2, 0, 1]
];
$matrix = createAdjacencyMatrix(3, $edges);
echo "邻接矩阵:\n";
foreach ($matrix as $row) {
echo implode(" ", $row) . "\n";
}
$lcs = longestCommonSubsequence("ABCDGH", "AEDFHR");
echo "最长公共子序列长度: " . $lcs . "\n"; // 输出: 3
复杂度分析工具函数
// 复杂度分析工具类
class ComplexityAnalyzer
{
// 计算执行时间
public static function measureTime($function, ...$args)
{
$start = microtime(true);
$result = call_user_func_array($function, $args);
$end = microtime(true);
return [
'result' => $result,
'time' => $end - $start,
];
}
// 计算内存使用
public static function measureMemory($function, ...$args)
{
$memoryBefore = memory_get_usage();
$result = call_user_func_array($function, $args);
$memoryAfter = memory_get_usage();
return [
'result' => $result,
'memory' => $memoryAfter - $memoryBefore,
];
}
// 生成测试数据
public static function generateTestData($size, $type = 'random')
{
$data = [];
switch ($type) {
case 'sorted':
for ($i = 0; $i < $size; $i++) {
$data[] = $i;
}
break;
case 'reverse':
for ($i = $size - 1; $i >= 0; $i--) {
$data[] = $i;
}
break;
case 'random':
default:
for ($i = 0; $i < $size; $i++) {
$data[] = rand(1, $size * 10);
}
break;
}
return $data;
}
}
// 冒泡排序
function bubbleSort($arr)
{
$n = count($arr);
for ($i = 0; $i < $n; $i++) { // O(n)
for ($j = 0; $j < $n - $i - 1; $j++) { // O(n)
if ($arr[$j] > $arr[$j + 1]) {
// 交换元素
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
return $arr;
}
// 快速排序
function quickSort($arr)
{
if (count($arr) <= 1) {
return $arr;
}
$pivot = $arr[0];
$left = $middle = $right = [];
foreach ($arr as $value) { // O(n)
if ($value < $pivot) {
$left[] = $value;
} elseif ($value == $pivot) {
$middle[] = $value;
} else {
$right[] = $value;
}
}
return array_merge(
quickSort($left), // O(log n) 递归深度
$middle,
quickSort($right) // O(log n) 递归深度
);
}
// 归并排序 (需要额外空间)
function mergeSortWithSpace($arr)
{
$length = count($arr);
if ($length <= 1) {
return $arr;
}
$mid = (int)($length / 2);
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid);
$left = mergeSortWithSpace($left);
$right = mergeSortWithSpace($right);
return mergeArrays($left, $right); // 需要O(n)额外空间
}
function mergeArrays($left, $right)
{
$result = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] <= $right[$j]) {
$result[] = $left[$i++];
} else {
$result[] = $right[$j++];
}
}
// 添加剩余元素
while ($i < count($left)) {
$result[] = $left[$i++];
}
while ($j < count($right)) {
$result[] = $right[$j++];
}
return $result;
}
// 使用示例
function testSortingAlgorithms()
{
$testData = ComplexityAnalyzer::generateTestData(1000);
// 测试冒泡排序
$bubbleResult = ComplexityAnalyzer::measureTime('bubbleSort', $testData);
echo "冒泡排序时间: " . $bubbleResult['time'] . " 秒\n";
// 测试快速排序
$quickResult = ComplexityAnalyzer::measureTime('quickSort', $testData);
echo "快速排序时间: " . $quickResult['time'] . " 秒\n";
// 测试内存使用
$memoryResult = ComplexityAnalyzer::measureMemory('mergeSortWithSpace', $testData);
echo "归并排序内存使用: " . $memoryResult['memory'] . " 字节\n";
}
// 运行测试
testSortingAlgorithms();
复杂度总结表
// 复杂度参考表
class ComplexityReference {
public static function getReferenceTable() {
return [
'O(1)' => [
'name' => '常数时间',
'description' => '执行时间固定，与输入规模无关',
'examples' => ['数组访问', '哈希表查找', '数学运算'],
'php_functions' => ['array_push', 'array_pop', 'isset']
],
'O(log n)' => [
'name' => '对数时间',
'description' => '每次操作将问题规模减半',
'examples' => ['二分查找', '平衡二叉树操作'],
'php_functions' => ['array_search (有序数组)']
],
'O(n)' => [
'name' => '线性时间',
'description' => '执行时间与输入规模成正比',
'examples' => ['数组遍历', '查找最大值', '链表遍历'],
'php_functions' => ['array_map', 'array_filter', 'foreach']
],
'O(n log n)' => [
'name' => '线性对数时间',
'description' => '高效排序算法的基准',
'examples' => ['归并排序', '快速排序', '堆排序'],
'php_functions' => ['usort', 'uasort', 'uksort']
],
'O(n²)' => [
'name' => '平方时间',
'description' => '通常涉及嵌套循环',
'examples' => ['冒泡排序', '选择排序', '插入排序'],
'php_functions' => ['嵌套的foreach循环']
],
'O(2ⁿ)' => [
'name' => '指数时间',
'description' => 'n稍大就不可行',
'examples' => ['斐波那契(朴素递归)', '子集生成'],
'php_functions' => []
],
'O(n!)' => [
'name' => '阶乘时间',
'description' => '最慢的复杂度之一',
'examples' => ['全排列生成', '旅行商问题(暴力法)'],
'php_functions' => []
]
];
}
}
// 显示复杂度参考表
$reference = ComplexityReference::getReferenceTable();
foreach ($reference as $complexity => $info) {
echo "{$complexity} - {$info['name']}\n";
echo "描述: {$info['description']}\n";
echo "示例: " . implode(", ", $info['examples']) . "\n";
if (!empty($info['php_functions'])) {
echo "PHP函数: " . implode(", ", $info['php_functions']) . "\n";
}
echo "---\n";
}
输出
O(1) - 常数时间
描述: 执行时间固定，与输入规模无关
示例: 数组访问, 哈希表查找, 数学运算
PHP函数: array_push, array_pop, isset
---
O(log n) - 对数时间
描述: 每次操作将问题规模减半
示例: 二分查找, 平衡二叉树操作
PHP函数: array_search (有序数组)
---
O(n) - 线性时间
描述: 执行时间与输入规模成正比
示例: 数组遍历, 查找最大值, 链表遍历
PHP函数: array_map, array_filter, foreach
---
O(n log n) - 线性对数时间
描述: 高效排序算法的基准
示例: 归并排序, 快速排序, 堆排序
PHP函数: usort, uasort, uksort
---
O(n²) - 平方时间
描述: 通常涉及嵌套循环
示例: 冒泡排序, 选择排序, 插入排序
PHP函数: 嵌套的foreach循环
---
O(2ⁿ) - 指数时间
描述: n稍大就不可行
示例: 斐波那契(朴素递归), 子集生成
---
O(n!) - 阶乘时间
描述: 最慢的复杂度之一
示例: 全排列生成, 旅行商问题(暴力法)
---
这个PHP实现版完整地展示了各种时间复杂度和空间复杂度的具体实例，包含了：
- 完整的代码实现 - 所有算法都用PHP语法实现
- 详细的注释说明 - 每个函数都标注了复杂度
- 实际的测试用例 - 可以直接运行查看结果
- 性能分析工具 - 可以测量执行时间和内存使用
- 实际应用对比 - 展示不同复杂度算法的实际差异