时间复杂度空间复杂度
目录
时间复杂度空间复杂度
一、时间复杂度
时间复杂度（Time Complexity）表示算法运行时间随输入规模增长的变化趋势。通常用大 O 表示法（Big O Notation）来描述。
常见时间复杂度
| 复杂度 | 名称 | 例子 |
| O(1) | 常数时间复杂度 | 访问数组中的某个元素。 |
| O(log n) | 对数时间复杂度 | 二分查找。 |
| O(n) | 线性时间复杂度 | 遍历数组或链表。( 一重循环 ) |
| O(n log n) | 线性对数时间复杂度 | 快速排序、归并排序。 |
| O(n²) | 平方时间复杂度 | 冒泡排序、选择排序（ 双重循环 ） |
| O(2ⁿ) | 指数时间复杂度 | 递归求解斐波那契数列（未优化）。 |
| O(n!) | 阶乘时间复杂度 | 旅行商问题（穷举所有排列）。 |
例子
- O(1)：常数时间复杂度
int getFirstElement(int[] arr) {
return arr[0]; // 无论数组多大，只需一次操作
}- O(n)：线性时间复杂度
void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) { // 遍历数组，操作次数与数组长度成正比
System.out.println(arr[i]);
}
}- O(n²)：平方时间复杂度
void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1; j++) { // 双重循环，操作次数与数组长度的平方成正比
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}- O(log n)：对数时间复杂度
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}二、空间复杂度
空间复杂度（Space Complexity）表示算法运行过程中所需的额外存储空间随输入规模增长的变化趋势。通常也用大 O 表示法描述。
常见空间复杂度
| 复杂度 | 名称 | 例子 |
| O(1) | 常数空间复杂度 | 只使用固定数量的变量。 |
| O(n) | 线性空间复杂度 | 使用一个与输入规模成正比的数组或列表。 |
| O(n²) | 平方空间复杂度 | 使用一个二维数组（如邻接矩阵）。 |
例子
- O(1)：常数空间复杂度
int sum(int a, int b) {
return a + b; // 只使用了固定数量的变量（a 和 b）
}- O(n)：线性空间复杂度
int[] copyArray(int[] arr) {
int[] newArr = new int[arr.length]; // 创建了一个与输入数组大小相同的新数组
for (int i = 0; i < arr.length; i++) {
newArr[i] = arr[i];
}
return newArr;
}- O(n²)：平方空间复杂度
int[][] createMatrix(int n) {
int[][] matrix = new int[n][n]; // 创建了一个 n x n 的二维数组
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = i + j;
}
}
return matrix;
}三. 如何分析时间复杂度和空间复杂度
时间复杂度分析
找出基本操作：通常是循环、递归、条件判断等。
计算基本操作的执行次数：通常与 输入规模 （如数组长度
n）有关。用大 O 表示法表示：忽略常数项和低阶项。
void printPairs(int[] arr) {
for (int i = 0; i < arr.length; i++) { // O(n)
for (int j = 0; j < arr.length; j++) { // O(n)
System.out.println(arr[i] + ", " + arr[j]); // O(1)
}
}
}总时间复杂度：O(n) * O(n) * O(1) = O(n²)。
空间复杂度分析
找出额外存储空间：通常是变量、数组、递归栈等。
计算存储空间的大小：通常与 输入规模（如数组长度
n） 有关。用大 O 表示法表示：忽略常数项和低阶项。
例子
int[] reverseArray(int[] arr) {
int[] result = new int[arr.length]; // O(n)
for (int i = 0; i < arr.length; i++) {
result[i] = arr[arr.length - 1 - i];
}
return result;
}总空间复杂度：O(n)（用于存储 result 数组）。
- 总结
时间复杂度：衡量 算法运行时间 随输入规模增长的变化趋势。
空间复杂度：衡量 算法运行过程中所需的额外存储空间 随输入规模增长的变化趋势。
大 O 表示法：忽略常数项和低阶项，关注增长趋势。
谢谢deepseek,存个档