什么是算法的空间复杂度和时间复杂度，分别怎么衡量。

1. 时间复杂度

时间复杂度衡量的是算法运行时间与输入规模之间的关系。它通常用大O记号（Big O Notation）表示，例如 O(1)、O(n)、O(n2) 等。

衡量方法：

• 常数时间复杂度 O(1)：无论输入规模如何，算法的执行时间是固定的。

• 线性时间复杂度 O(n)：算法的执行时间与输入规模成正比。

• 平方时间复杂度 O(n2)：算法的执行时间与输入规模的平方成正比。

• 对数时间复杂度 O(logn)：算法的执行时间与输入规模的对数成正比。

2. 空间复杂度

空间复杂度衡量的是算法运行过程中额外占用的内存空间与输入规模之间的关系。它也用大O记号表示。

衡量方法：

• 常数空间复杂度 O(1)：算法运行过程中只占用固定数量的额外空间。

• 线性空间复杂度 O(n)：算法运行过程中占用的额外空间与输入规模成正比。

• 平方空间复杂度 O(n2)：算法运行过程中占用的额外空间与输入规模的平方成正比。

---

示例：C语言程序

示例1：线性搜索（时间复杂度 O(n)，空间复杂度 O(1)）

#include <stdio.h>int linearSearch(int arr[], int n, int target) {for (int i = 0; i < n; i++) {  // 遍历数组，时间复杂度 O(n)if (arr[i] == target) {return i;  // 找到目标值，返回索引}}return -1;  // 未找到目标值，返回 -1
}int main() {int arr[] = {10, 20, 30, 40, 50};int n = sizeof(arr) / sizeof(arr[0]);int target = 30;int result = linearSearch(arr, n, target);if (result != -1) {printf("Element found at index %d\n", result);} else {printf("Element not found\n");}return 0;
}

分析：

• 时间复杂度：O(n)，因为算法需要遍历整个数组。

• 空间复杂度：O(1)，因为算法只使用了常量级的额外空间（变量 i 和 result）。

---

示例2：冒泡排序（时间复杂度 O(n2)，空间复杂度 O(1)）

#include <stdio.h>void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {  // 外层循环 n-1 次for (int j = 0; j < n - i - 1; j++) {  // 内层循环 n-i-1 次if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;  // 交换相邻元素}}}
}void printArray(int arr[], int n) {for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("Original array: ");printArray(arr, n);bubbleSort(arr, n);printf("Sorted array: ");printArray(arr, n);return 0;
}

分析：

• 时间复杂度：O(n2)，因为算法包含两层嵌套循环。

• 空间复杂度：O(1)，因为算法只使用了常量级的额外空间（变量 i、j 和 temp）。

---

示例3：递归实现的斐波那契数列（时间复杂度 O(2n)，空间复杂度 O(n)）

#include <stdio.h>int fibonacci(int n) {if (n <= 1) {return n;  // 基本情况}return fibonacci(n - 1) + fibonacci(n - 2);  // 递归调用
}int main() {int n = 10;printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));return 0;
}

分析：

• 时间复杂度：O(2n)，因为递归树的深度为 n，每个节点都有两个分支。

• 空间复杂度：O(n)，因为递归调用栈的最大深度为 n。

---

总结

• 时间复杂度：衡量算法的运行时间，通常用大O记号表示。

• 空间复杂度：衡量算法运行过程中占用的额外内存空间，也用大O记号表示。

• 在实际开发中，时间和空间复杂度需要综合考虑，以选择最适合问题的算法。