【数据结构】时间复杂度-C语言版(二)

简介: 【数据结构】时间复杂度-C语言版

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是计算程序占用了多少字节的空间,算的是变量的个数,也使用大O渐进表示法。

举例1:

1. //计算冒泡排序的空间复杂度
2. #define  _CRT_SECURE_NO_WARNINGS  1
3. #include<stdio.h>
4. #include<assert.h>
5. void Swap(int *p1, int *p2) 
6. {
7.  int temp = *p1;
8.  *p1 = *p2;
9.  *p2 = temp;
10. }
11. 
12. void BubbleSort(int* a,int n)
13. {
14.   assert(a);
15.   int end = 0;
16.   for (end = n; end > 0; --end)
17.   {
18.     int exchange = 0;
19.     for (int i = 1; i < end; i++)
20.     {
21.       if (a[i - 1] > a[i])
22.       {
23.         Swap(&a[i - 1], &a[i]);
24.         exchange = 1;
25.       }
26.     }
27. 
28.     if (exchange == 0)
29.     {
30.       break;
31.     }
32.   }
33. }

计算空间复杂度时,不考虑输入数组的空间,计算的是算法运行中额外使用的空间。对于时间来说,是累计的,但是空间是不累计的,可以复用的(如定义了一个end变量,当执行for循环end不断--时,依旧使用end变量的空间)。该算法定义了4个变量:end、exchage、i、temp,因此额外使用了4个空间,即额外使用了常数个空间,根据大O渐进表示法,空间复杂度为O(1)。

举例2:

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. long long* Fibonacci(size_t n)
4. {
5.  if (n == 0)
6.  {
7.    return NULL;
8.  }
9. 
10.   long long* fibArray = (long long*)malloc(sizeof(long long) * (n + 1));
11.   fibArray[0] = 0;
12.   fibArray[1] = 1;
13.   for (int i = 2; i <= n; i++)
14.   {
15.     fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
16.   }
17. 
18.   return fibArray;
19. }

动态开辟了n+1个空间,空间复杂度为O(N)。


递归算法空间复杂度的计算

递归算法的空间复杂度等于递归的深度(递归的层数),递归多少层就建立多少个栈帧,每建立一个栈帧空间复杂度就是O(1),即建立常数个空间

1. long long Factorial(size_t N)
2. {
3.  return N < 2 ? N : Factorial(N - 1) * N;
4. }

递归的层数为N,空间复杂度为O(N)。

空间复杂度应用

1.力扣网-移除元素

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。

分析:空间复杂度为O(1),即不允许创建额外数组,在原数组上进行操作。可以使用快慢指针的原理,当快指针当前指向的元素值如果不等于val,对快指针+1,如果等于val,将快指针的值赋给慢指针,将快指针和慢指针都+1。

代码:

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. 
4. int removeElement(int* nums, int numsSize, int val) 
5. {
6.  if (numsSize == 0)
7.  {
8.    return 0;
9.  }
10.   int src = 0;
11.   int dst = 0;
12. 
13.   int i = 0;
14.   for (i = 0; i < numsSize; i++)
15.   {
16.     if (nums[i] != val)
17.     {
18.       nums[dst] = nums[src];
19.       src++;
20.       dst++;
21.     }
22.     else
23.     {
24.       src++;
25.     }
26.   }
27.   return dst;
28. }
29. 
30. int main()
31. {
32.   int arr[] = { 6,3,2,5,2,1,3,2 };
33.   int len = sizeof(arr) / sizeof(arr[0]);
34.   int i = 0;
35.   int ret = removeElement(arr, len, 2);
36.   for (i = 0; i < ret; i++)
37.   {
38.     printf("%d ", arr[i]);
39.   }
40.   return 0;
41. }

执行结果:

2.力扣网-删除有序数组中的重复项

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

要求不要使用额外的数组空间,你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

分析:要求不要使用额外的数组空间,就必须在原数组上进行操作。使用3个指针,cur指向数组不同元素的第一个,next寻找下一个不同的元素,dst指向新的存放的不同元素的位置。当next和cur指向的元素值不同时,就把next指向的元素存放到dst的位置,cur、next、dst都++,当next和cur指向的元素值相同时,next++直到next指向的元素和cur指向的元素不相等,将dst++,cur=next,next++

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. int removeDuplicates(int* nums, int numsSize) 
4. {
5.  if (numsSize == 0)
6.  {
7.    return 0;
8.  }
9. 
10.   int cur = 0;
11.   int next = 1;
12.   int dst = 0;
13.   while (next < numsSize)
14.   {
15.     if (nums[next] != nums[cur])
16.     {
17.       nums[dst++] = nums[cur++];
18.       next++;
19.     }
20.     else
21.     {
22.       //nums[next] = nums[cur],不用做操作,next++,直到nums[next] != nums[cur]
23.       while ((next < numsSize) && (nums[next] == nums[cur]))
24.       {
25.         next++;
26.       }
27. 
28.       //现在nums[next] != nums[cur],nums[dst] = nums[cur]
29.       nums[dst] = nums[cur];
30. 
31.       //dst向后移动一个位置
32.       dst++;
33. 
34.       //cur直接移动到next的位置
35.       cur = next;
36. 
37.       //next向后移动一个位置
38.       next++;
39. 
40.     }
41.   }
42. 
43.   //当next走完整个数组后,直接将cur位置的值赋值给dst++位置
44.   if (cur < numsSize)
45.   {
46.     nums[dst++] = nums[cur];
47.   }
48.   return dst;
49. }
50. int main()
51. {
52.   int arr[] = { 1,1,2,3,4,4,9,9,9,10 };
53.   int len = sizeof(arr) / sizeof(arr[0]);
54.   int ret = removeDuplicates(arr, len);
55. 
56.   int i = 0;
57.   for (i = 0; i < ret; i++)
58.   {
59.     printf("%d ", arr[i]);
60.   }
61.   return 0;
62. }

执行结果:

相关文章
|
4天前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
22天前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
3月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
94 1
|
3月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
99 1
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
81 4
|
3月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
63 4
|
3月前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
63 4
|
3月前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现,涵盖二叉树的层次遍历及广度优先搜索(BFS)和深度优先搜索(DFS)的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点;BFS利用队列从源节点逐层遍历图节点,适用于最短路径等问题;DFS通过递归或栈深入图的分支,适合拓扑排序等场景。这些算法是数据结构和算法学习的基础,对提升编程能力和解决实际问题至关重要。
68 4
|
3月前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现,涵盖链表与二叉树操作,包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法,解决了理论与实际应用中的常见问题,有助于提升编程能力和数据结构理解。
59 4

热门文章

最新文章