引言
在计算机科学中，是解决问题的核心工具。当我们设计或选择一个算法时，通常需要考虑两个关键因素：时间复杂度和空间复杂度。这两个指标帮助我们衡量算法的效率和资源消耗情况。本文将深入探讨C语言中常见的数据结构及其相关算法的复杂度分析，并通过代码示例进行具体说明。那现在，一起来看看吧！！！
正文
一 时间复杂度
1. 常数时间复杂度 O(1)
例：
#include <stdio.h>
int getElement(int arr[], int index, int size) {
if (index >= 0 && index < size) {
return arr[index]; // 直接访问数组元素，时间复杂度为O(1)
} else {
return -1; // 错误处理
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
printf("%d
", getElement(arr, 2, 5)); // 输出3
return 0;
}
2. 线性时间复杂度 O(n)
例·：
#include <stdio.h>
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]); // 遍历数组，时间复杂度为O(n)
}
printf("
");
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
printArray(arr, 5); // 输出整个数组
return 0;
}
3. 对数时间复杂度 O(log n)
例·：
#include <stdio.h>
int binarySearch(int arr[], int target, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // 找到目标，返回索引
} else if (arr[mid] < target) {
left = mid + 1; // 在右半部分继续搜索
} else {
right = mid - 1; // 在左半部分继续搜索
}
}
return -1; // 未找到目标
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int target = 7;
int result = binarySearch(arr, target, 0, 9);
if (result != -1) {
printf("Found %d at index %d
", target, result);
} else {
printf("%d not found in array
", target);
}
return 0;
}
4. 平方时间复杂度 O(n^2)
冒泡排序示例：
#include <stdio.h>
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("
");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, size);
printf("Sorted array:
");
printArray(arr, size);
return 0;
}
5. 指数时间复杂度 O(2^n)
// 未经优化的斐波那契数列计算
#include <stdio.h>
int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
int main() {
int n = 10;
printf("Fibonacci number is %d
", fibonacci(n));
return 0;
}
二 空间复杂度
（1）空间复杂度的定义与重要性
（2）常见的空间复杂度类型及介绍
1.常数空间复杂度 O(1)
例如，一个简单的交换两个整数值的函数：
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int main() {
int x = 5, y = 10;
swap(&x, &y);
printf("x = %d, y = %d
", x, y); // 输出: x = 10, y = 5
return 0;
}
在这个例子中，swap 函数只使用了一个额外的变量 temp 来存储临时值，因此它的空间复杂度是 O(1)。
2.线性空间复杂度 O(n)
例如，一个计算数组中所有元素之和的函数：
#include <stdio.h>
int sumArray(int arr[], int size) {
int sum = 0;
for (int i = 0; i < size; i++) {
sum += arr[i];
}
return sum;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Sum = %d
", sumArray(arr, size)); // 输出: Sum = 15
return 0;
}
这里，除了几个固定大小的变量（如 sum 和循环计数器 i）外，没有使用额外的内存。但是，由于我们假设数组本身占用的空间也计入空间复杂度（尽管它是作为输入提供的），所以整个程序的空间复杂度可以视为 O(n)（其中 n 是数组的大小）。然而，仅就 sumArray 函数而言，其额外使用的空间仍然是 O(1)。
3.多项式空间复杂度 O(n^k)（k为常数）
例如，打印一个 n×n 矩阵的元素：
#include <stdio.h>
void printMatrix(int matrix[][10], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", matrix[i][j]);
}
printf("
");
}
}
int main() {
int matrix[10][10] = { /* 初始化矩阵 */ };
// 假设矩阵已经以某种方式被填充
printMatrix(matrix, 10); // 这里 n 被硬编码为 10，但一般情况下可以是任何正整数
return 0;
}
注意：
- 在这个例子中，我为了简化而假设矩阵的第二维大小为常量
10（这是不常见的做法，通常我们会让两个维度都是可变的）。在实际应用中，更常见的做法是声明一个完全可变的二维数组或使用动态内存分配。即使这样，如果我们考虑矩阵本身所占用的空间，那么空间复杂度仍然是O(n^2)。
4. 动态分配的内存（可变空间复杂度）
当使用 malloc、calloc 或 realloc 等函数动态分配内存时，空间复杂度可能变得不那么直观。它取决于运行时决定分配的内存量。例如：
#include <stdio.h>
#include <stdlib.h>
void createAndFillArray(int **array, int size) {
*array = (int *)malloc(size * sizeof(int));
if (*array == NULL) {
fprintf(stderr, "Memory allocation failed
");
exit(EXIT_FAILURE);
}
for (int i = 0; i < size; i++) {
(*array)[i] = i * i; // 例如，用平方值填充数组
}
}
int main() {
int size = 100; // 可以根据需要改变大小
int *array = NULL;
createAndFillArray(&array, size);
// 使用数组...
free(array); // 不要忘记释放分配的内存！
return 0;
}
在这个例子中，createAndFillArray 函数根据传入的 size 参数动态分配一个整数数组。因此，该函数的空间复杂度是 O(size)，即 O(n)（如果我们将 size 视为输入 n参数）。注意，这里的空间复杂度是指除了输入参数和固定大小的变量之外额外分配的内存量。
（3）空间复杂度的分析方法
分析算法的空间复杂度时，需要考虑以下几个方面：
综上所述：
空间复杂度是衡量算法内存效率的重要指标之一。通过了解不同类型的空间复杂度及其特点和分析方法，可以选择最合适的算法来解决特定问题，从而提高系统性能。
三 空间复杂度与时间复杂度的关系
四 常见算法的复杂度分析
1. 线性搜索
代码展示：
#include <stdio.h>
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // 找到目标值，返回索引
}
}
return -1; // 未找到目标值，返回-1
}
int main() {
int arr[] = {2, 4, 6, 8, 10};
int target = 6;
int result = linearSearch(arr, 5, target);
if (result != -1) {
printf("Element found at index %d
", result);
} else {
printf("Element not found in the array
");
}
return 0;
}
-
时间复杂度：
O(n)
在最坏情况下，需要比较n次才能找到目标值或确定其不存在。因此，线性搜索的时间复杂度为O(n)。 -
空间复杂度：
O(1)
除了输入数组和几个辅助变量外，不需要额外的存储空间。因此，空间复杂度为O(1)。
2. 二分搜索
代码展示：
#include <stdio.h>
int binarySearch(int arr[], int size, int target) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // 找到目标值，返回索引
} else if (arr[mid] < target) {
left = mid + 1; // 在右半部分继续搜索
} else {
right = mid - 1; // 在左半部分继续搜索
}
}
return -1; // 未找到目标值，返回-1
}
int main() {
int arr[] = {2, 4, 6, 8, 10};
int target = 6;
int result = binarySearch(arr, 5, target);
if (result != -1) {
printf("Element found at index %d
", result);
} else {
printf("Element not found in the array
");
}
return 0;
}
-
时间复杂度：
O(log n)
每次迭代都将搜索范围减半，因此二分搜索的时间复杂度为O(log n)，其中n是数组的大小。 -
空间复杂度：
O(1)
同样地，除了输入数组和几个辅助变量外，不需要额外的存储空间。因此，空间复杂度为O(1)。
3. 冒泡排序
#include <stdio.h>
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换arr[j]和arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("
");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
printf("Sorted array:
");
printArray(arr, size);
return 0;
}
-
时间复杂度：
O(n^2)
在最坏情况下，需要进行n*(n-1)/2次比较和可能的交换操作，因此冒泡排序的时间复杂度为O(n^2)。 -
空间复杂度：
O(1)
冒泡排序是原地排序算法，不需要额外的存储空间。因此，空间复杂度为O(1)。