网站后台放在哪里,做网站的公司倒闭了,大专学计算机我后悔了,三北防护林体系建设网站今天开始数据结构的学习#xff01;作为一大重点#xff0c;拿出态度很重要#xff0c;想要真实掌握#xff0c;博客笔记自然少不了#xff01;重点全部上色#xff01;避免疏忽
下面我们从0基础开始学习今天的第一节#xff01;不用担心看不懂#xff0c;拒绝枯燥的理…
今天开始数据结构的学习作为一大重点拿出态度很重要想要真实掌握博客笔记自然少不了重点全部上色避免疏忽
下面我们从0基础开始学习今天的第一节不用担心看不懂拒绝枯燥的理论概念 目录
对“算法”的理解
“算法复杂度”概念理解 一 时间复杂度的表示与计算 一.1 时间复杂度实例讲解 一.2 “约会”预期管理类时间复杂度 一.3 “约会”预期管理类时间复杂度实例讲解 一.4 时间复杂度的意义
二 空间复杂度的表示与计算 二.1 空间复杂度实例讲解 对“算法”的理解
算法简而言之就是解决问题的步骤跟指令通过一系列操作从而达到预期的结果 “算法复杂度”概念理解
哈是算法复杂度
概念度量算法性能优劣的一个量级说明
度量算法主要从两个方面来考虑时间复杂度 空间复杂度 时间复杂度作用体现执行这个算法所需要的计算工作量下面是完整概念 比如对2个算法进行比较若算法A较算法B更加快此时指它的时间复杂度更好 空间复杂度作用体现执行这个算法所需要占用的额外的内存空间大小下面是完整概念 下面我们分别来进行讲解 一 时间复杂度的表示与计算
表示首先它的表示用大O符号表示On这个n下面参考例题详解表示这个问题的 一个工序规模次数 On也叫大O表示法
计算规则 1用常数1来取代运行时间中所有加法常数 2只要高阶项不要低阶项 3不要高阶项系数
常见的时间复杂度复杂度由低到高 O1 常数阶 On 线性阶 On^2 平方阶 Ologn 对数阶 Onlogn nlogn阶 On^3 立方阶 O2^n 指数阶
画图演示 一.1 时间复杂度实例讲解 实例1 第一步我们计算出这个工程的工序次数是 2*N10 次
第二步根据计算规则进行删除 只要高阶项不要低阶项去除10首先得到2*N 不要高阶项系数去除2最后得到N
第三步得出最终结果Func2的时间复杂度为 ON 实例2 第一步计算这个工程的执行工序得到MN 次
第二步根据计算规则进行删除更改 因为M与N都是未知数因为最高阶阶数相同也无常数 故全部保留
第三步得出时间复杂度OMN 实例3 第一步计算这个工程的总工序得到100 次
第二步根据计算规则进行更改与删除 用常数1取代所有加法常数100改为1最终得到1 注这个“1”代表常数次不是代表1次
第三步得到时间复杂度O1 一.2 “约会”预期管理类时间复杂度
难道跟“约会”有关吗没错没错下面如果是你和你的对象约会你会选择哪个时间点 最早下午1700 大概下午19:00 最迟下午20:00
我们来分析一下因为这只是一个引入所以无法符合每个人的想法啊
如果我们把对每件事的期望尽量拉小那么当这件事不管完没完成对你的打击也就越小
如果失败那么我的期望也没那么高管的他呢
如果成功带给我的期望是不是更多一些 下面我们针对非直接性需要分情况考虑的对时间复杂度的计算
另外一些时间复杂度存在几种考虑情况比如计算什么时候可以从一堆字符串找到一个对应字符
有以下几种情况 直接一次找到这属于最好情况下界 找到末尾才找到这属于最坏情况上界 最坏与最好平均下来就是平均情况
那么我们假设一个长为N的字符串对应几种情况分别是1次 N次 N/2次
在实际情况中一般关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为ON取最坏情况 一.3 “约会”预期管理类时间复杂度实例讲解 实例1 第一步得到这个问题的最坏工序次数为 7 次
第二步根据计算规则进行删除与更改 用常数1取代所有加法常数7改为1
第三步得到Srchr的时间复杂度为 O1 实例2 第一步计算这个问题的最坏情况下执行次数为N^2也就是N的平方
第二步根据计算规则进行删除与更改 与三条规则不冲突不用更改
第三步得到它的时间复杂度为 ON^2 实例3
二分查找涉及数学逻辑下面配有演示 第一步计算这个问题最坏情况工序为 logN也就是log以2为底的N的对数
第二步根据计算规则删除与更改 与三条规则不冲突直接保留
第三步得出时间复杂度为 OlogN
我们看数学演示计算过程假设N是数组个数x表示最坏查找数
查询次数记录1N/22N/2/23N/2/2/2xN/2^x
我们发现每查询一次就需要除一次2 那么查询x次就表示N/2^x 有2^xN注意查一次有一个2那么查了x次就是2^x数组有N个元素那么最 坏情况就是N2^x 那么最坏查找数 xlog2N
由于log以2为底的N的对数不好写这个底数所以规定凡是以2为底的对数可以直接写为logN
注只适用于以2为底的对数 可以写为 logN底数2可以不写 实例4
斐波那契数的计算下图配有数学解析 第一步计算这个问题的最坏工序次数 第二步 根据计算规则进行删除与更改 去除高阶项系数2^N-12^N * 2^-1最终得2^N
第三步得到时间复杂度 O2^N 一.4 时间复杂度的意义
学会时间复杂度的计算可以更理解题目的要求以及比较平时代码的性能比如 我们可以看到上面有时间复杂度的限制那么我们在写题目时需要先大概计算一下时间复杂度 二 空间复杂度的表示与计算
空间复杂度我们之前已经大概了解了一下 运行算法过程中额外占用存储空间大小的量度
表示与时间复杂度类似还是用大O表示法On其中n表示变量个数n一般等于变量个数额外开辟次数不是字节数
计算依然遵循时间复杂度的三条原则
注意函数运行时所需要的栈空间存储参数、局部变量、一些寄存器信息等等在编译器期间已经确定好了因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定 投机取巧一般空间复杂度大多是O1与On两种情况遇到其它的概率很小
下面我们来进行实例讲解 二.1 空间复杂度实例讲解 实例1 第一步计算图中的变量个数以及看是否额外占用空间 发现创建了3个变量并没有额外开创空间带 i 的循环是在n里面的所以 i 用的是n开 辟的那个空间没有重新开辟
第二步按照三条规则重新删除与更改常数项改为1 O3也就变成了O1
第三步得出空间复杂度为O1 实例2 第一步分析变量个数与额外开辟空间大小 变量个数额外开辟空间 第二步计算 额外占用存储空间大小为On11 按照三个规则进行删除与更改只要高阶项不要低阶项改为On
第三步得出空间复杂度 On 实例3 第一步计算变量个数以及额外占用的空间 每次调用函数都需要开辟空间一共调用了N1次 这个空间的开辟是计算开辟次数不是字节 第二步根据三条规则进行删除与更改不要地阶项只保留高阶项 ON1更变为 ON
第三步空间复杂度为 ON 以上就是 算法复杂度 的全部讲解了写的好的话记得一键三连哦希望每天都是阳光明媚
