一、时间复杂度（Time Complexity）

时间复杂度衡量的是算法执行所需的时间，它通常表示为输入数据的规模 ( n ) 的函数。

1. 基本概念

• 大O符号（Big O Notation）：用来描述算法的时间复杂度的上界，表示最坏情况下的时间增长趋势。
• 常见的时间复杂度：
  • ( O(1) )：常数时间复杂度，不随输入规模变化。
  • ( O(log n) )：对数时间复杂度，常见于二分查找。
  • ( O(n) )：线性时间复杂度，常见于简单遍历算法。
  • ( O(n log n) )：线性对数时间复杂度，常见于快速排序、归并排序。
  • ( O(n²) )：平方时间复杂度，常见于嵌套循环。
  • (O(2ⁿ) )：指数时间复杂度，常见于递归的组合问题。
  • ( O(n!) )：阶乘时间复杂度，常见于排列问题。

2. 计算方法

• 逐步分析法：分析算法的每一行代码，累加时间复杂度。
  • 赋值语句、算术运算、比较运算等基本操作的时间复杂度都是 ( O(1) )。
  • 对于循环结构，如果循环次数是 ( n )，那么该部分的时间复杂度是 ( O(n) )。
  • 对于嵌套循环，如果内外层分别有 ( n ) 次和 ( m ) 次，那么时间复杂度是 ( O(n \times m) )。
• 取最大量级：最终时间复杂度为各部分时间复杂度的最大值。忽略系数和低阶项。

3.示例

1.常数时间复杂度 O(1)

示例：

int a = 10;
int b = a + 5;

讲解：

无论输入数据的规模如何，上述代码中的每个操作都只需要常数时间。因此，这段代码的时间复杂度是 O(1) 。

2. 线性时间复杂度 O(n)

示例1：

c
复制代码
for (int i = 0; i < n; i++) {// O(1) 操作
}

讲解：

这里有一个简单的循环，循环执行了 n 次，每次循环执行 O(1) 的操作。因此，总时间复杂度是 O(n) 。

示例2：

for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {// O(1) 操作}
}

讲解：

在这个例子中，循环运行了 n 次，每次加法操作的时间复杂度是 O(1)。因此，总时间复杂度是 O(n) 。

3. 平方时间复杂度 O(n²)

示例1：

for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {// O(1) 操作}
}

讲解：

这是一个双重嵌套循环。外层循环执行n次，内层循环也执行 n 次，每次内层循环的操作时间复杂度是 O(1)。因此，总时间复杂度是 O(n×n) = O(n²) 。

示例2：

for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {// O(1) 操作}
}

讲解：

在这个例子中，内层循环的次数随外层循环的次数变化，第一次内层循环执行 n 次，第二次执行 n−1 次，以此类推，总时间复杂度为 O(n(n+1)/2) ，简化后依然为 O(n²)。

4. 对数时间复杂度 O(log n)

示例：

int binarySearch(int arr[], int n, int target) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] == target)return mid;else if (arr[mid] < target)low = mid + 1;elsehigh = mid - 1;}return -1;
}

讲解：

这是二分查找算法的实现 。在每次循环中，搜索区间都减半，因此时间复杂度为 O(log n) 。

5. 线性对数时间复杂度 O(n log n)

示例：

void mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m + 1, r);merge(arr, l, m, r);}
}

讲解：

归并排序是一种典型的 O(n log n) 时间复杂度算法。它将数组递归地分成两半，直到每个子数组只剩一个元素，然后再合并这些子数组。每次合并的复杂度是 O(n) ，递归深度是 O(log n) ，因此总时间复杂度为 O(n log n) 。

6. 指数时间复杂度 O(2ⁿ)

示例：

int fibonacci(int n) {if (n <= 1)return n;elsereturn fibonacci(n-1) + fibonacci(n-2);
}

讲解：

这里是递归计算斐波那契数列的代码。每次递归调用都需要计算两个子问题，导致时间复杂度为 O(2ⁿ) 。这种复杂度通常会导致非常长的执行时间，不适用于大规模数据。

二、空间复杂度（Space Complexity）

空间复杂度衡量的是算法执行过程中所需的存储空间，它表示为输入数据规模 ( n ) 的函数。

1. 基本概念

• 大O符号：同样使用大O符号表示，表示所需空间的增长趋势。
• 常见的空间复杂度：
  • ( O(1) )：常数空间复杂度，表示不随输入规模变化的额外空间需求。
  • ( O(n) )：线性空间复杂度，表示需要与输入规模成正比的空间。
  • ( O(n²) )：平方空间复杂度，表示需要与输入规模平方成正比的空间。

2. 计算方法

• 逐步分析法：分析算法中所需的存储空间，累加所有部分的空间复杂度。
  • 简单变量（如整型、浮点型）占用的空间是 ( O(1) )。
  • 数组、列表等数据结构占用的空间与其长度有关，例如一个长度为 ( n ) 的数组占用的空间是 ( O(n) )。
  • 递归调用时，需要考虑调用栈的空间开销。

3.示例

1. 常数空间复杂度 O(1)

示例：

int a = 5;
int b = 10;
int c = a + b;

讲解：

无论输入数据的规模如何，这段代码只占用了固定的内存空间。因此，空间复杂度是 O(1) 。

2. 线性空间复杂度 O(n)

示例1：

int arr[n];

讲解：

如果你声明了一个长度为 n 的数组，那么空间复杂度是 O(n) ，因为数组的大小随 n 的增加而增加。

示例2：

void createArray(int n) {int* arr = (int*)malloc(n * sizeof(int));
}

讲解：

在这个例子中，通过 malloc 分配的内存空间大小为 n 个整数的大小，因此空间复杂度为 O(n) 。

3. 平方空间复杂度 O(n²)

示例：

int matrix[n][n];

讲解：

这里声明了一个 n×n 的矩阵，因此空间复杂度为O(n²) ，因为存储该矩阵所需的空间随 n 的平方增长。

4. 指数空间复杂度 O(2ⁿ)

示例：

void allSubsets(int arr[], int n) {int subset_count = pow(2, n);for (int i = 0; i < subset_count; i++) {for (int j = 0; j < n; j++) {if (i & (1 << j))printf("%d ", arr[j]);}printf("\n");}
}

讲解：

生成一个集合的所有子集需要存储 2ⁿ 个子集。每个子集都可能占用额外的存储空间，导致总体空间复杂度为 O(2ⁿ) 。

三、总结

• 时间复杂度 主要关注的是算法运行的时间随输入规模的变化趋势。
• 空间复杂度 主要关注的是算法执行过程中所需的额外存储空间。