东莞做网站 动点官网,百度开户流程,学校网站建设用哪个系统,搜索引擎seo推广各位读者老爷好#xff01;现在鼠鼠我呀来浅谈一下数据结构初阶中的一个知识点#xff1a;算法的时间复杂度和空间复杂度#xff0c;希望对你有所帮助。 在浅谈时间复杂度和空间复杂度之前#xff0c;咱们可以来了解一下一下几个概念#xff1a;
1.什么是数据结构 数据结…各位读者老爷好现在鼠鼠我呀来浅谈一下数据结构初阶中的一个知识点算法的时间复杂度和空间复杂度希望对你有所帮助。 在浅谈时间复杂度和空间复杂度之前咱们可以来了解一下一下几个概念
1.什么是数据结构 数据结构(Data Structure)是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。 其实简单来说吧。数据结构就是在内存中管理数据。 拓展 1.什么是数据库 简单来说数据库就是在磁盘中管理数据。 2.内存和磁盘的异同 同内存和磁盘都是电脑的两个核心存储介质都是存储数据的两个硬件。 异内存的速度快需要带电存储磁盘的速度相对慢不带电存储。 比如我们在电脑中创建一个文本文档在该文档中输入数据在数据没有保存之前如果电脑突然关机了那我们重启电脑后这些数据就没有了因为这些数据是在内存中存储的内存却需要带电存储。但如果我们在电脑关机之前保存了这些数据重启之后打开文本文档还可以看到数据因为保存的数据已经到了磁盘中了磁盘无需带电存储。不考虑文本文档有自动保存的情况。 2.什么是算法 算法(Algorithm):就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。 咱们再简单来说。算法就是对数据做各种处理的方法。 那咱们如何判断一个算法的好坏呢
算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。。
3.时间复杂度
3.1时间复杂度的概念
时间复杂度的定义在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。
那时间复杂度该如何计算呢 咱们来抛砖引玉一下子哈分析一下下面代码的时间复杂度
void Func1(int N)//计算Fun1中count总共执行多少次
{
int count 0;
for (int i 0; i N ; i)
{
for (int j 0; j N ; j)
{
count;
}
}
for (int k 0; k 2 * N ; k)
{
count;
}
int M 10;
while (M--)
{
count;
}
printf(%d\n,count);咱们为了方便介绍鼠鼠我直接揭晓答案这个函数的时间复杂度是O(N^2)
那为什么是O(N^2)呢什么是O(N)呢这就要看下面的知识了
3.2大O的渐近表示法
实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。 大O符号Big O notation是用于描述函数渐进行为的数学符号。 推导大O阶方法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。 上面的解释其实意思就是说我们计算时间复杂度用的是大O的渐近表示法表示时间复杂度都是用O(?)表示的至于括号里面的问号? 该用什么替代我们就要根据推导大O阶方法具体分析了咱们来分析一下上面的代码看看。
函数Func1中count的基本操作次数是一个函数F(N)N^22*N10。根据推导大O阶方法我们可以知道Func1的时间复杂度是O(N^2)。其实推导大O阶方法意思就是去掉那些对结果影响不大的项推导大O阶方法的思想精髓就是估算。
咱们分析一个代码的时间复杂度看看
int Func2(int*nums,int numsSize,int n)
{
int i0;
for(i0;inumsSize;i)
{
if(*(numsi)n)
{
return i;
}
}
return -1;
} 咱们看看这个函数Func2中是写不出那个操作次数的函数的操作次数有三种情况 最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界) 咱看这个函数Func2无非就是一种遍历数组的算法在数组nums的numsSize个元素中遍历找n找到了返回下标找不到返回-1。最好情况1次就找到了平均情况numsSize/2次找到了最坏情况numsSize次找到了。 所以这个函数的时间复杂度是O(N)因为时间复杂度是保守的估算取最坏情况。
3.3常见时间复杂度举例分析
上面两个代码计算时间复杂度都是看代码的内容好像在数循环次数就行。其实不然看一个算法的时间复杂度要看算法思想无需了解代码细节咱们在下面代码来体会。
实例1
// 计算Func3的时间复杂度
void Func3(int N)
{
int count 0;
for (int k 0; k 2 * N ; k)
{
count;
}
int M 10;
while (M--)
{
count;
}
printf(%d\n, count);
}
咱们看这个算法基本操作执行了2N10次所以这个时间复杂度是O(N)。为什么不是O(2N)呢推导大O阶方法第3条可以知道要去除常数2。举个例子如果有一颗距离地球100亿光年的适合居住的星球和距离地球200亿光年的适合居住的星球对于人类来说没有区别因为人类远行距离的量级能达到百亿光年的话多一个百亿是无所谓的这里去除常数2就是这个思想。
实例2
// 计算Func4的时间复杂度
void Func4(int N, int M)
{
int count 0;
for (int k 0; k M; k)
{
count;
}
for (int k 0; k N ; k)
{
count;
}
printf(%d\n, count)
}
这个算法基本操作执行了MN次有两个未知数M和N时间复杂度为 O(NM)也可以写成O(max(N,M))。
实例3
// 计算Func5的时间复杂度
void Func5(int N)
{
int count 0;
for (int k 0; k 100; k)
{
count;
}
printf(%d\n, count);
}
这个算法基本操作执行了10次也就是常数次通过推导大O阶方法第1条时间复杂度为 O(1)。
实例4
// 计算BubbleSort的时间复杂度
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end n; end 0; --end)
{
int exchange 0;
for (size_t i 1; i end; i)
{
if (a[i-1] a[i])
{
Swap(a[i-1], a[i]);
exchange 1;
}
}
if (exchange 0)
break;
}这里是一个冒泡排序这个算法呢基本操作执行最好N次最坏执行了(N*(N1)/2次通过推导大O阶方法时间复杂度一般看最坏时间复杂度为 O(N^2)。
实例5
// 计算BinarySearch的时间复杂度
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin 0;
int end n-1;
// [begin, end]begin和end是左闭右闭区间因此有号
while (begin end)
{
int mid begin ((end-begin)1);
if (a[mid] x)
begin mid1;
else if (a[mid] x)
end mid-1;
else
return mid;
}
return -1;
}
这里是一个二分查找。基本操作执行最好1次最坏O(logN)次每查找1次可以排除一半最好情况当然是第1次就找到最坏情况得查到最后1次最后1次是第几次呢我们一共查找了x次因为每找1次N就除1个2所以N2^x所以最坏要查找xx等于log以2为底以N为指数次。所以时间复杂度为O(logN)。
pslogN在算法分析中默认表示是底数为2对数为N。所以这个底数2可以省略但以其他数为底就不能省略。
根据二分查找算法的时间复杂度O(logN)来看二分查找是一个很牛的算法因为根据这个算法就算是有1百万个数据最多查找20次就够了。但二分查找又不是很牛因为这个算法有一个致命缺陷就是要求数据必须有序。
实例6
/ 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{
if(0 N)
return 1;
return Fac(N-1)*N;
}
咱看这是一个求阶乘的函数。这个函数算法思想无非就是当传参不为0时递归调用函数自己 。那基本调用调用了N1次时间累加N1次所以时间复杂度是O(N)。
实例7
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{
if(N 3)
return 1;
return Fib(N-1) Fib(N-2);
}
这是一个递归求斐波那契数的函数。算法思想是双路递归类似细胞分裂1生22生4……。 所以时间复杂度是O(2^N)。
根据这个时间复杂度O(2^N)我们可以知道这个算法求斐波那契数不是一个好算法因为指数爆炸太费时间了。那我们采用什么算法求斐波那契数更优呢鼠鼠我这里写一个代码
int Fib(size_t N)
{if (N 1 || N 2){return 1;}int i1 1, i2 1, i3 0;int j 0;for (j 0; j N - 2;j){i3 i1 i2;i1 i2;i2 i3;}return i3;
}
咱们这个代码求斐波那契数的算法就比上面的代码好这个算法根据思想可知时间复杂度是O(N)。相比于递归算法大大节省时间。所以我们写代码之前需考虑好各种算法的时间复杂度再考虑用哪种算法写代码能让代码更加优质。
4.空间复杂度
4.1空间复杂度的概念
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
4.2常见的空间复杂度举例分析
实例1
// 计算BubbleSort的空间复杂度
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end n; end 0; --end)
{
int exchange 0;
for (size_t i 1; i end; i)
{
if (a[i-1] a[i])
{
Swap(a[i-1], a[i]);
exchange 1;
}
}
if (exchange 0)
break;
}
}
咱们知道这是一个冒泡排序嘛那上面代码实现这个算法逻辑的需要额外开辟了常数个1个空间 就是exchange所以空间复杂度是O(1)。
实例2
// 计算Fibonacci的空间复杂度
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
if(n0)
return NULL;
long long * fibArray (long long *)malloc((n1) * sizeof(long long));
fibArray[0] 0;
fibArray[1] 1;
for (int i 2; i n ; i)
{
fibArray[i] fibArray[i - 1] fibArray [i - 2];
}
return fibArray;
}
这个算法逻辑的实现需要动态开辟malloc了n1块空间所以空间复杂度为 O(N)。
实例3
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{
if(N 0)
return 1;
return Fac(N-1)*N;
} 这个算法递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间。空间复杂度为O(N)。
5.复杂度的oj练习
消失的数字OJ链接https://leetcode-cn.com/problems/missing-number-lcci/。打开链接可以做这道题哈
这道题要求时间在O(N)中完成鼠鼠我呀有2种解法咱们依次写写
解法1
int missingNumber(int* nums, int numsSize){int sum(0numsSize)*(numsSize1)/2;int i0;for(i0;inumsSize;i){sum-*(numsi);}return sum;
}
这个解题思路就是利用等差数列公式求出0到n所有整数之和再用这个和依次减去数组元素得到的就是消失的数字呗这个时间复杂度妥妥是O(N)空间复杂度是O(1)oj是可以通过的大家可以去试试鼠鼠我就不展示了哈!
解法2
int missingNumber(int* nums, int numsSize){int missnum0,i0;for(i0;inumsSize;i){missnum^i;}for(i0;inumsSize;i){missnum^nums[i];}return missnum;
}
这个解题思路是利用0^任何数任何数、任何数^任何数0这两个特点 得到的。这个时间复杂度也是O(N)空间复杂度也是O(1)oj也是可以通过的 6.ending
鼠鼠我呀才疏学浅如有不足恳请斧正
懂我意思吧
