【数据结构】时间复杂度和空间复杂度是什么？
时间复杂度和空间复杂度是评估算法性能的两个关键指标，它们帮助我们衡量算法在不同输入规模下的效率。时间复杂度描述了算法执行所需的时间，空间复杂度则描述了算法运行时所需的内存（存储空间）。理解和计算时间复杂度和空间复杂度对设计高效的算法至关重要。
1. 时间复杂度（Time Complexity）
1.1 定义
时间复杂度衡量的是算法执行所需的时间随输入规模（n）的增长情况。它描述的是最坏情况下，算法在输入规模增加时，所需要执行的基本操作（如赋值、比较、循环等）的增长率。
时间复杂度通常使用大O符号来表示，表示随着输入大小的增大，算法的执行时间如何增长。常见的时间复杂度有：
- O(1)：常数时间
- O(log n)：对数时间
- O(n)：线性时间
- O(n log n)：线性对数时间
- O(n²)：平方时间
- O(2^n)：指数时间
- O(n!)：阶乘时间
1.2 计算方法
计算时间复杂度的步骤：
-
确定基本操作：找出算法中的主要操作，例如比较、赋值、循环等。通常来说，这些操作的执行次数是计算时间复杂度的关键。
-
分析控制结构：
- 对于顺序结构，各部分的时间复杂度直接相加。
- 对于条件结构（如if-else），选择最坏情况的分支进行分析。
- 对于循环结构，循环执行次数对时间复杂度影响最大。
-
忽略低阶项和常数：在计算结果中，只保留最具增长率的项，忽略常数和较小的低阶项。例如，对于
O(n + n^2)，只需保留最高阶项，即 O(n²)。
1.3 示例
例1：常数时间复杂度 O(1)
int findFirst(int arr[], int n) {
return arr[0];
}
这个函数的时间复杂度为 O(1)，因为它只执行了一次操作，与输入大小无关。
例2：线性时间复杂度 O(n)
int sum(int arr[], int n) {
int total = 0;
for(int i = 0; i < n; i++) {
total += arr[i];
}
return total;
}
该算法遍历了整个数组，循环执行了 n 次，因此时间复杂度是 O(n)。
例3：平方时间复杂度 O(n²)
void printPairs(int arr[], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d, %d", arr[i], arr[j]);
}
}
}
这个算法有两个嵌套的循环，内外循环分别执行 n 次，总的执行次数是 n * n，即 O(n²)。
例4：对数时间复杂度 O(log n)
int binarySearch(int arr[], int n, int target) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
时间复杂度：O(log n)，因为每次搜索会将搜索范围缩小一半。
空间复杂度：O(1)，只需要几个变量来保存索引和目标值，不会随着输入规模增加而增加额外空间。
例5：线性对数时间复杂度 O(n log n)
void merge(int arr[], int l, int m, int r) {
// 合并两个子数组
}
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(n)，需要额外的数组来存储排序过程中的临时结果。
例6：指数时间复杂度 O(2^n)
int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
时间复杂度：O(2^n)，因为每次调用都会进行两个递归调用，导致指数级的增长。
空间复杂度：O(n)，递归的深度等于 n，因此栈空间是 O(n)。
例7：阶乘时间复杂度 O(n!)
void permute(char[] arr, int l, int r) {
if (l == r) {
// 输出排列
} else {
for (int i = l; i <= r; i++) {
swap(arr[l], arr[i]);
permute(arr, l + 1, r);
swap(arr[l], arr[i]); // 回溯
}
}
}
时间复杂度：O(n!)，生成所有可能的排列组合时，每次递归调用都会交换数组中的元素。
空间复杂度：O(n)，递归调用栈的深度为 n。
2. 空间复杂度（Space Complexity）
2.1 定义
空间复杂度衡量的是算法在运行过程中所需内存空间的大小，通常关注的是变量、数据结构、递归栈等所占用的空间。它同样使用大O符号表示，用来描述随着输入规模增长，所需空间的增长率。
空间复杂度可以分为：
- 固定空间：不依赖于输入大小的空间（如常量、变量），通常为 O(1)。
- 输入相关空间：依赖于输入规模的空间（如数组、递归栈），其空间复杂度通常与输入 n 有关。
2.2 计算方法
计算空间复杂度的步骤：
-
统计变量占用空间：计算算法中所有变量占用的空间。如果有数组或列表等结构，计算它们占用的内存。
-
分析递归栈空间：对于递归算法，考虑递归调用过程中栈空间的消耗。
-
忽略常数：同时间复杂度计算一样，忽略常数项和较小的低阶项，保留最高增长率的项。
2.3 示例
例1：常数空间复杂度 O(1)
int add(int a, int b) {
int sum = a + b;
return sum;
}
这个函数只使用了常量空间来存储 a、b 和 sum，所以它的空间复杂度是 O(1)。
例2：线性空间复杂度 O(n)
int* createArray(int n) {
int* arr = (int*)malloc(n * sizeof(int));
return arr;
}
在这个例子中，算法为长度为 n 的数组分配了空间，因此空间复杂度是 O(n)。
例3：递归算法的空间复杂度 O(n)
int factorial(int n) {
if (n == 1) return 1;
return n * factorial(n - 1);
}
由于递归调用的栈空间会随着递归深度增加，因此这个算法的空间复杂度是 O(n)。
3. 时间复杂度与空间复杂度的关系
在设计算法时，我们经常需要在时间复杂度和空间复杂度之间做权衡。例如，通过增加空间开销，可以降低时间复杂度（如使用哈希表）。反之，为了减少空间使用，可能需要增加算法执行时间。因此，选择合适的算法往往需要考虑任务的优先级。
常见例子：
- 快速排序（Quick Sort）：时间复杂度 O(n log n)，空间复杂度 O(log n)。
- 归并排序（Merge Sort）：时间复杂度 O(n log n)，但空间复杂度是 O(n)，因为它需要额外的存储空间来存放中间数组。
4. 总结
- 时间复杂度：衡量算法执行的时间随输入规模的增长情况，常见的有 O(1), O(n), O(n²) 等。
- 空间复杂度：衡量算法运行时所需内存空间的大小，常见的有 O(1), O(n) 等。
- 计算方法：主要通过分析算法中的控制结构（如循环、递归）来确定时间复杂度，分析变量和数据结构的空间占用来确定空间复杂度。
理解时间复杂度和空间复杂度能够帮助我们评估和优化算法，使得在处理大规模数据时能够保持较高的效率。
原文地址：https://blog.csdn.net/qq_37945670/article/details/142954798
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！