数据结构 时间空间复杂

目录一、数据结构前言1数据结构2算法3数据结构和算法的重要性二、算法效率1复杂度的概念三、时间复杂度1大O 的渐进表示法2时间计算例题四、空间复杂度1空间计算例题一、数据结构前言1数据结构数据结构(Data Structure)是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用所以我们要学各式各样的数据结构如线性表、树、图、哈希等。2算法算法就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。3数据结构和算法的重要性无论在考研还是在公司面试的时候数据结构都会考到因此学习数据结构是对应每一个计算机专业学生来说是非常中要的存在。二、算法效率1复杂度的概念算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。就像干活一样如果有好的办法又能快速解决又不麻烦的办法就不会选择有难的又费时的办法。而时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。三、时间复杂度时间复杂度是一个代码来衡量的复杂度的其中只有通常我们定义函数TN。代码展示void test(int* N) { for(int i0;iN;i) { for(int j0;jN;j) { printf(%d ,j); } printf(\n); } for(int i0;iN;i) { printf(%d ,i); } printf(%d,1); return; }用函数计算时间复杂度TNN^2N1但是代码的时间复杂度是ON^2。1大O 的渐进表示法test 执行的代码中当N1 TN111当N10 TN100101当N100TN100001001……当Nn TNN^2N1当N足够大的时候影响最大的是N^2 ,而N 和1 的影响几乎微小可以之间、省略不计所以时间复杂度为ON推导⼤O阶规则1.时间复杂度函数式T(N)中只保留最⾼阶项去掉那些低阶项因为当N不断变⼤时 低阶项对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。2.如果最⾼阶项存在且不是1则去除这个项⽬的常数系数因为当N不断变⼤这个系数对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。3.T(N)中如果没有N相关的项⽬只有常数项⽤常数1取代所有加法常数。2时间计算例题例题1void test(int N) { int count0; for(int i0;i2N;i) { count; } for(int i0;i10;i) { count; } }TN2N10ON例题2void test(int N,int M) { int count0; for(int i0;i2N;i) { count; } for(int i0;iM;i) { count; } }T(N)NMO(N)例题3void test() { int count0; for(int i0;i100;i) { count; } for(int i0;i10;i) { count; } }T(N)110O(1)例题4void test(int N) { int n1; while(nN) { n*2; } }T(N)log2 NO(log2 n)四、空间复杂度空间复杂度也是用来计算代码复杂度之一它与时间复杂度类似但有所不同例如时间复杂度为ON空间复杂度O1那么就是 1 个人在时间为 N 做的事情在相同时间复杂度时空间复杂度ON那么就是 N 个人在时间为 N 做的事情。而这个人就是空间复杂度就是在同时间内要申请的空间大小。空间复杂度计算时与时间复杂度计算一致的。1空间计算例题冒泡排序tpyedef int SLDataType; typedef struct SeqList { SLDataType* arr; int size; int capacity; }SL; void spaw(SLDataType* arr) { SLDataType tmp *arr; *arr *(arr 1); *(arr 1) tmp; return; } void SL_bubble_sort(SL* sl)//冒泡排序升序 { for (int i 0; i sl-size; i) { int flag 1; for (int j 0; j sl-size - i - 1; j) { if (sl-arr[j] sl-arr[j 1]) { spaw(sl-arr[j]); flag 0; } } if (flag) break; } }那么冒泡排序在时间复杂度为ON^2以为在函数相同时间内每次只申请了一个int整形的tmp而空间复杂度为O(1)递归Nlong long Fac(size_t N) { if(N 0) return 1; return Fac(N-1)*N; }Fac递归调⽤了N次额外开辟了N个函数栈帧 每个栈帧使⽤了常数个空间因此空间复杂度为O(N)