IT评测·应用市场-qidao123.com

标题: 从C语言看数据结构和算法：复杂度决定性能 [打印本页]

---

作者: 祗疼妳一个    时间: 2025-1-23 10:40
标题: 从C语言看数据结构和算法：复杂度决定性能
大家好，这里是小编的博客频道
小编的博客：就爱学编程
    很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同劳绩更好的本身！！！
  
  
引言

在计算机科学中，算法是解决问题的核心工具。当我们计划或选择一个算法时，通常需要考虑两个关键因素：时间复杂度和空间复杂度。这两个指标帮助我们权衡算法的服从和资源斲丧情况。本文将深入探究C语言中常见的数据结构及其相关算法的复杂度分析，并通过代码示例进行具体阐明。那现在，一起来看看吧！！！

---

   那接下来就让我们开始遨游在知识的海洋！
  正文

---

一 时间复杂度

   

• 定义：时间复杂度是权衡算法实行时间长短的一个标准，它反映了算法随着输入规模增大而增长的趋势。通常用“大O符号”（O-notation）来表示。
  

  

---

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

   

• 常数时间复杂度意味着无论输入规模如何变革，算法的实行时间都保持稳定。比方，访问数组中的某个元素就是O(1)操作。
  

  例：

2. #include <stdio.h>
4. int getElement(int arr[], int index, int size) {
5.     if (index >= 0 && index < size) {
6.         return arr[index]; // 直接访问数组元素，时间复杂度为O(1)
7.     } else {
8.         return -1; // 错误处理
9.     }
10. }
12. int main() {
13.     int arr[] = {1, 2, 3, 4, 5};
14.     printf("%d
15. ", getElement(arr, 2, 5)); // 输出3
16.     return 0;
17. }

复制代码

---

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

   

• 线性时间复杂度表示算法的实行时间与输入规模成正比。比方，遍历一个数组的所有元素就是O(n)操作。
  

  例·：

2. #include <stdio.h>
4. void printArray(int arr[], int size) {
5.     for (int i = 0; i < size; i++) {
6.         printf("%d ", arr[i]); // 遍历数组，时间复杂度为O(n)
7.     }
8.     printf("
9. ");
10. }
12. int main() {
13.     int arr[] = {1, 2, 3, 4, 5};
14.     printArray(arr, 5); // 输出整个数组
15.     return 0;
16. }

复制代码

---

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

   

• 对数时间复杂度常见于二分查找等基于分治计谋的算法中。其特点是指数级减少的搜索范围。
  

  例·：

2. #include <stdio.h>
4. int binarySearch(int arr[], int target, int left, int right) {
5.     while (left <= right) {
6.         int mid = left + (right - left) / 2;
7.         if (arr[mid] == target) {
8.             return mid; // 找到目标，返回索引
9.         } else if (arr[mid] < target) {
10.             left = mid + 1; // 在右半部分继续搜索
11.         } else {
12.             right = mid - 1; // 在左半部分继续搜索
13.         }
14.     }
15.     return -1; // 未找到目标
16. }
18. int main() {
19.     int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
20.     int target = 7;
21.     int result = binarySearch(arr, target, 0, 9);
22.     if (result != -1) {
23.         printf("Found %d at index %d
24. ", target, result);
25.     } else {
26.         printf("%d not found in array
27. ", target);
28.     }
29.     return 0;
30. }

复制代码

---

4. 平方时间复杂度 O(n^2)

   

• 平方时间复杂度通常出现在嵌套循环结构中，如冒泡排序和选择排序。
  

  冒泡排序示例：

1. #include <stdio.h>
3. void bubbleSort(int arr[], int size) {
4.     for (int i = 0; i < size - 1; i++) {
5.         for (int j = 0; j < size - i - 1; j++) {
6.             if (arr[j] > arr[j + 1]) {
7.                 // 交换元素
8.                 int temp = arr[j];
9.                 arr[j] = arr[j + 1];
10.                 arr[j + 1] = temp;
11.             }
12.         }
13.     }
14. }
16. void printArray(int arr[], int size) {
17.     for (int i = 0; i < size; i++) {
18.         printf("%d ", arr[i]);
19.     }
20.     printf("
21. ");
22. }
24. int main() {
25.     int arr[] = {64, 34, 25, 12, 22, 11, 90};
26.     int size = sizeof(arr)/sizeof(arr[0]);
27.     bubbleSort(arr, size);
28.     printf("Sorted array:
29. ");
30.     printArray(arr, size);
31.     return 0;
32. }

复制代码

---

5. 指数时间复杂度 O(2^n)

   

• 指数时间复杂度通常出现在递归调用未进行优化且问题规模迅速增大的情况下，如斐波那契数列的直接递归实现。
  

2. // 未经优化的斐波那契数列计算
3. #include <stdio.h>
5. int fibonacci(int n) {
6.     if (n <= 1) {
7.         return n;
8.     } else {
9.         return fibonacci(n - 1) + fibonacci(n - 2);
10.     }
11. }
13. int main() {
14.     int n = 10;
15.     printf("Fibonacci number is %d
16. ", fibonacci(n));
17.     return 0;
18. }

复制代码

---

二 空间复杂度

（1）空间复杂度的定义与紧张性

   

• 空间复杂度（Space Complexity）是对一个算法在运行过程中临时占用存储空间巨细的量度。它反映了算法在实行过程中对内存利用的需求，是评价算法服从的紧张指标之一。与时间复杂度雷同，空间复杂度也利用大O记号来渐进地表示。
  

  

---

（2）常见的空间复杂度范例及介绍

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

   

• 算法所需的额外空间是一个常数，与输入规模无关。这意味着不随着输入数据的增长而增长额外的存储空间。比方，在交换变量的操作中，只利用了一个额外的变量temp，无论输入的数据是什么规模，都只需要常数级别的额外空间。
  

  比方，一个简朴的交换两个整数值的函数：

1. #include <stdio.h>
3. void swap(int *a, int *b) {
4.     int temp = *a;
5.     *a = *b;
6.     *b = temp;
7. }
9. int main() {
10.     int x = 5, y = 10;
11.     swap(&x, &y);
12.     printf("x = %d, y = %d
13. ", x, y); // 输出: x = 10, y = 5
14.     return 0;
15. }

复制代码

在这个例子中，swap 函数只利用了一个额外的变量 temp 来存储临时值，因此它的空间复杂度是 O(1)。

---

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

   

• 算法所需的额外空间与输入规模成线性关系。比方，需要一个与输入规模相等的数组来存储数据，或者递归函数中每次调用都会占用一定的栈空间，调用次数与输入参数n成线性关系。常见的具有线性空间复杂度的算法包罗复制数组、字符串拼接等。
  

  比方，一个计算数组中所有元素之和的函数：

1. #include <stdio.h>
3. int sumArray(int arr[], int size) {
4.     int sum = 0;
5.     for (int i = 0; i < size; i++) {
6.         sum += arr[i];
7.     }
8.     return sum;
9. }
11. int main() {
12.     int arr[] = {1, 2, 3, 4, 5};
13.     int size = sizeof(arr) / sizeof(arr[0]);
14.     printf("Sum = %d
15. ", sumArray(arr, size)); // 输出: Sum = 15
16.     return 0;
17. }

复制代码

这里，除了几个固定巨细的变量（如 sum 和循环计数器 i）外，没有利用额外的内存。但是，由于我们假设数组本身占用的空间也计入空间复杂度（尽管它是作为输入提供的），所以整个步伐的空间复杂度可以视为 O(n)（此中 n 是数组的巨细）。然而，仅就 sumArray 函数而言，其额外利用的空间仍旧是 O(1)。

---

3.多项式空间复杂度 O(n^k)（k为常数）

   

• 算法所需的额外空间与输入规模的幂次关系成正比。比方，某些嵌套循环算法可能需要二维数组，导致空间复杂度为O(n^2)。这类算法的空间需求随着输入规模的增长而迅速增长。
  

  

---

比方，打印一个 n×n 矩阵的元素：

1. #include <stdio.h>
3. void printMatrix(int matrix[][10], int n) {
4.     for (int i = 0; i < n; i++) {
5.         for (int j = 0; j < n; j++) {
6.             printf("%d ", matrix[i][j]);
7.         }
8.         printf("
9. ");
10.     }
11. }
13. int main() {
14.     int matrix[10][10] = { /* 初始化矩阵 */ };
15.     // 假设矩阵已经以某种方式被填充
16.     printMatrix(matrix, 10); // 这里 n 被硬编码为 10，但一般情况下可以是任何正整数
17.     return 0;
18. }

复制代码

注意：

• 在这个例子中，我为了简化而假设矩阵的第二维巨细为常量 10（这是不常见的做法，通常我们会让两个维度都是可变的）。在实际应用中，更常见的做法是声明一个完全可变的二维数组或利用动态内存分配。即使这样，假如我们考虑矩阵本身所占用的空间，那么空间复杂度仍旧是 O(n^2)。
  

---

4. 动态分配的内存（可变空间复杂度）

当利用 malloc、calloc 或 realloc 等函数动态分配内存时，空间复杂度可能变得不那么直观。它取决于运行时决定分配的内存量。比方：

1. #include <stdio.h>
2. #include <stdlib.h>
4. void createAndFillArray(int **array, int size) {
5.     *array = (int *)malloc(size * sizeof(int));
6.     if (*array == NULL) {
7.         fprintf(stderr, "Memory allocation failed
8. ");
9.         exit(EXIT_FAILURE);
10.     }
11.     for (int i = 0; i < size; i++) {
12.         (*array)[i] = i * i; // 例如，用平方值填充数组
13.     }
14. }
16. int main() {
17.     int size = 100; // 可以根据需要改变大小
18.     int *array = NULL;
19.     createAndFillArray(&array, size);
20.     // 使用数组...
21.     free(array); // 不要忘记释放分配的内存！
22.     return 0;
23. }

复制代码

在这个例子中，createAndFillArray 函数根据传入的 size 参数动态分配一个整数数组。因此，该函数的空间复杂度是 O(size)，即 O(n)（假如我们将 size 视为输入 n参数）。注意，这里的空间复杂度是指除了输入参数和固定巨细的变量之外额外分配的内存量。

---

（3）空间复杂度的分析方法

分析算法的空间复杂度时，需要考虑以下几个方面：
   

• 算法本身所占用的存储空间：这取决于算法书写的长短和所利用的数据结构。
  

   

• 输入输出数据所占用的存储空间：这是由要解决的问题决定的，不随算法的不同而改变。
  

   

• 算法在运行过程中临时占用的存储空间：这是随算法的不同而异的，也是空间复杂度分析的重点。需要关注算法在实行过程中是否需要额外的辅助空间，以及这些空间的增长情况。
  

  综上所述：

• 空间复杂度是权衡算法内存服从的紧张指标之一。通过了解不同范例的空间复杂度及其特点和分析方法，可以选择最合适的算法来解决特定问题，从而进步系统性能。
  

---

三 空间复杂度与时间复杂度的关系

   

• 时间复杂度和空间复杂度是算法的两个紧张性能指标，它们之间存在一定的权衡关系。有时为了追求较好的时间复杂度，可能会牺牲一定的空间复杂度；反之亦然。因此，在计划算法时需要根据具体问题的需求和资源限制进行综合考虑。
  

  

---

四 常见算法的复杂度分析

1. 线性搜索

   

• 线性搜索是一种简朴的查找算法，它逐个检查列表中的元素，直到找到目标值或遍历完整个列表。
  

  代码展示：

2. #include <stdio.h>
4. int linearSearch(int arr[], int size, int target) {
5.     for (int i = 0; i < size; i++) {
6.         if (arr[i] == target) {
7.             return i; // 找到目标值，返回索引
8.         }
9.     }
10.     return -1; // 未找到目标值，返回-1
11. }
13. int main() {
14.     int arr[] = {2, 4, 6, 8, 10};
15.     int target = 6;
16.     int result = linearSearch(arr, 5, target);
17.     if (result != -1) {
18.         printf("Element found at index %d
19. ", result);
20.     } else {
21.         printf("Element not found in the array
22. ");
23.     }
24.     return 0;
25. }

复制代码

• 时间复杂度：O(n)
  在最坏情况下，需要比较n次才能找到目标值或确定其不存在。因此，线性搜索的时间复杂度为O(n)。
  
• 空间复杂度：O(1)
  除了输入数组和几个辅助变量外，不需要额外的存储空间。因此，空间复杂度为O(1)。
  

---

2. 二分搜索

   

• 二分搜索要求输入数组是有序的，它通过不停将搜索范围减半来快速定位目标值。
  

  代码展示：

2. #include <stdio.h>
4. int binarySearch(int arr[], int size, int target) {
5.     int left = 0, right = size - 1;
6.     while (left <= right) {
7.         int mid = left + (right - left) / 2;
8.         if (arr[mid] == target) {
9.             return mid; // 找到目标值，返回索引
10.         } else if (arr[mid] < target) {
11.             left = mid + 1; // 在右半部分继续搜索
12.         } else {
13.             right = mid - 1; // 在左半部分继续搜索
14.         }
15.     }
16.     return -1; // 未找到目标值，返回-1
17. }
19. int main() {
20.     int arr[] = {2, 4, 6, 8, 10};
21.     int target = 6;
22.     int result = binarySearch(arr, 5, target);
23.     if (result != -1) {
24.         printf("Element found at index %d
25. ", result);
26.     } else {
27.         printf("Element not found in the array
28. ");
29.     }
30.     return 0;
31. }

复制代码

• 时间复杂度：O(log n)
  每次迭代都将搜索范围减半，因此二分搜索的时间复杂度为O(log n)，此中n是数组的巨细。
  
• 空间复杂度：O(1)
  同样地，除了输入数组和几个辅助变量外，不需要额外的存储空间。因此，空间复杂度为O(1)。
  

---

3. 冒泡排序

   冒泡排序是一种简朴的排序算法，通过重复遍历要排序的数列，一次比较两个元素，假如它们的次序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止。

1. #include <stdio.h>
3. void bubbleSort(int arr[], int size) {
4.     for (int i = 0; i < size - 1; i++) {
5.         for (int j = 0; j < size - i - 1; j++) {
6.             if (arr[j] > arr[j + 1]) {
7.                 // 交换arr[j]和arr[j+1]
8.                 int temp = arr[j];
9.                 arr[j] = arr[j + 1];
10.                 arr[j + 1] = temp;
11.             }
12.         }
13.     }
14. }
16. void printArray(int arr[], int size) {
17.     for (int i = 0; i < size; i++) {
18.         printf("%d ", arr[i]);
19.     }
20.     printf("
21. ");
22. }
24. int main() {
25.     int arr[] = {64, 34, 25, 12, 22, 11, 90};
26.     int size = sizeof(arr) / sizeof(arr[0]);
27.     bubbleSort(arr, size);
28.     printf("Sorted array:
29. ");
30.     printArray(arr, size);
31.     return 0;
32. }

复制代码

• 时间复杂度：O(n^2)
  在最坏情况下，需要进行n*(n-1)/2次比较和可能的交换操作，因此冒泡排序的时间复杂度为O(n^2)。
  
• 空间复杂度：O(1)
  冒泡排序是原地排序算法，不需要额外的存储空间。因此，空间复杂度为O(1)。
  

---

快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4