全国网站建设公,模板大全免费,高端效果图制作公司,重庆网站建设推广服务前言 C语言这块算是总结完了#xff0c;那从本篇开始就是步入一个新的大章——数据结构#xff0c;这篇我们先来认识一下数据结构有关知识#xff0c;以及复杂度的相关知识 个人主页#xff1a;小张同学zkf 若有问题 评论区见 感兴趣就关注一下吧 目录 1.什么是数据结构 2.… 前言 C语言这块算是总结完了那从本篇开始就是步入一个新的大章——数据结构这篇我们先来认识一下数据结构有关知识以及复杂度的相关知识 个人主页小张同学zkf 若有问题 评论区见 感兴趣就关注一下吧 目录 1.什么是数据结构 2.什么是算法
3.算法的复杂度
3.1时间复杂度 3.2三种情况
3.3空间复杂度 1.什么是数据结构
数据结构是计算机存储组织数据的方式指的是相互之间存在一种或多种特定关系的数据元素的集合 2.什么是算法
数据结构离不开算法那算法是什么东西那简单来说是一个定义好的计算过程。就是取一个或一组值输入并产生出一个或一组值作为输出当中产生的的计算步骤用来将输入数据转化成输出结果 3.算法的复杂度
算法在编写成可执行程序后运行时需要耗费时间资源和空间资源因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度
时间复杂度主要衡量一个算法的快慢而空间复杂度主要衡量一个算法运行的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度所以我们如今已经不需要在特别关注一个算法的空间复杂度。
3.1时间复杂度
时间复杂度的定义在计算机科学中算法的时间复杂度是一个函数注这里的函数是数学上的函数不是c语言的函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序跑起来才能知道但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方法。一个算法所花费的的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度
即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。 //请计算一下Func1中count语句总共执行了多少次?
void Funcl(int N)
{
int count 0;
for(int i0;iN;i)
{
for(int j0;jN;j)
{
count;
}
}for (int k0;k2*N;k)
{
count;
}
int M10;
while(M--)
{
count;
}
printf(%d\n,count);
}上面的时间复杂度是多少
我们用数学函数来表示来看第一个函数两个for循环那执行次数是不是就是N的平方次再看第二个函数执行2N次最后一个函数执行10次
那就是FNN^22*N10 精算值 估算值 N10 F(N)130 100 N100 F(N)10210 10000 N1000 F(N)1002010 1000000 实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法
那么要求大概值哪个表达式对次数影响最大呢是不是N^2 最大我么可以这样想一下如果N越来越大后面俩表达式2*N和10是不是对时间复杂度影响越来越小我们取极限那后面俩就没影响只有N^2对次数影响特别大所以只保留这一项我们也可以从这里看出来若为多项式我们只取次数高的那一项
那么这个函数的时间复杂度为ON^2 这也就是大O的渐进表示法
那我们再来看一个例子巩固一下
//计算Func3的时间复杂度?
void Func3(int N,int M)
{
int count 0;
for (int k0;kM;k)
{
count;
}
}
for (int k0;kN;k)
{
count;
}
printf(%d\n,count); 我们还是先用函数表示 FNNM
这下就有疑问了那这个用大O怎么表示 我们可以看一下这里没有明确说明N远大于M还是M远大于N都没有明确说明那就是对执行次数影响是同等的谁都不能舍去所以结果为ONNM
我们再来看一个
//计算Func4的时间复杂度?
void Func4(int N)
{
int count 0;
for (int k 0;k100;k)
{
count;
}
printf(%d\n,count);
}
这个时间复杂度又是多少呢
我们乍一看这次执行次数可以直接看出来一共执行了100次
那大O怎么表示那其实在大O里常数全部用1来表示所以结果为ON1
一定要注意这里这里的结果1不是执行了一次而是代表常数次就是我们可以看出来的次数执行次数不是未知数的话那运行时间就是固定的所以它们的时间复杂度都是ON1 综上我们可得出推导大O的方法 1.用常数1取代运行时间中的所有加法常数 2.在修改后的运行次数函数中只保留最高阶项如果最高阶项存在且不是1则去除与这个项目相乘的常数也就是把系数去掉 3.O1不是代表1次是代表常数次 3.2三种情况
有些算法的时间复杂度存在最好、平均和最坏情况最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界) 例如在一个长度为N数组中搜索一个数据x 最好情况1次找到 最坏情况N次找到 平均情况N/2次找到 在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N) 我们来看一下这个函数是不是有点眼熟没错我们之前总结过的冒泡排序那它的时间复杂度该怎么求那我们要求它的最坏情况我们先想一想冒泡排序是怎么排序的是不是第一个数先进行挨个比较然后是第二个数字以此类推那我们第一个数字是不是要比较N-1次第二个数字就是N-2次……直到最后比较一次那把这些都加起来是不是就是我们的时间复杂度了那就是求等差数列的和函数为N*(N-1)/2,大O表示法取最高项结果为ON^2
我们继续看一个 这个是不是也是有点眼熟对我之前总结的猜数字游戏里的二分查找那它的时间复杂度是多少那我们先来想一想这个函数怎么实现的是每次查找缩小一半范围相当于除2查找一次除一次2那N次就是除N个2那时间复杂度不就是除2的次数嘛那不就是log2N嘛用大O表示就是O(N)log2N
我们再来看一个 还记得这个吧没错这个也是我之前总结的递归问题中的青蛙跳台阶——斐波那契数列这个时间复杂度又是什么那
我们看一下这个函数是不是递归一次执行一次但它一个函数内递归了两次那它接下来是不是像树状线一样一个函数分两个函数如图所示我们来找一下规律是不是从2^0到2^n-2
那把这些都加起来就是时间复杂度了 我们可以根据错位相减法得到2^n-1-1,用大O表示就是ON2^N
3.3空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时额外占用存储空间大小的量度。 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 这个空间复杂度是多少
我们来看一下这个函数开辟了一个数组空间以及一些变量的空间都是常数个所以用大O表示是ON1
继续看一个 这个空间复杂度是多少
这里函数运行时额外开了一个n1的空间这个空间就是它的空间复杂度用大O表示就是ON
再看一个递归 这个空间复杂度是多少
它运行时创立了N个函数栈帧所以它的结果为ON
我们来看一个复杂点的 这个时间复杂度我们知道了是O2^N空间复杂度那
这个我们要好好想想递归函数在创建函数栈帧的特点第一列的函数栈帧创建完调用完再销毁后几列的函数递归再用第一列的曾经函数栈帧所用的空间不会额外再开辟新的函数栈帧简单来说就是第一列函数递归的深度就是它的空间复杂度后面的函数递归在第一列函数栈帧用完销毁的空间基础上再重复利用这个空间进行第二次函数递归 我们要记住一点空间可以重复利用 不用累计计算
所以这个空间复杂度就是第一列函数递归开辟的空间用大O表示ON 结束语 这篇博客我们对数据结构有了基础的认识通过这篇博客我们以后写代码要考虑这个算法的效率问题尽量保证时间复杂度消耗低空间复杂度空间不浪费时间第一空间其次的想法研究出效率高的算法。 OK感谢观看
