WordPress个人网站搭建,wordpress 5.1.1漏洞,wordpress4.5漏洞,可以做分销的淘客网站本文将会以插入排序为例#xff0c;介绍算法与数据结构的基础部分。插入排序排序可以说是整个算法中最为基础#xff0c;最为重要的一部分#xff0c;而插入排序正是排序算法中最简单的一种解决办法。什么是排序问题#xff1f;输入#xff1a;n个数的一个序列 。输出介绍算法与数据结构的基础部分。插入排序排序可以说是整个算法中最为基础最为重要的一部分而插入排序正是排序算法中最简单的一种解决办法。什么是排序问题输入n个数的一个序列 。输出输入序列的一个排列 同时满足 。而插入排序的思路和我们平时打扑克时整理排序的思路非常类似。开始时我们手中没有牌然后我们每次从桌上拿走一张牌并将其插入到手中正确的位置直到我们将牌整理完成。何为正确的位置用规范一点的描述可以认为将第 n 张牌插入到已经排好序的 n-1 张牌中并保证插入后依然保持有序。这就是插入排序的核心理念。从感性上来说我们需要整理多少张牌就对应着需要插入几次当然第一次插入时因为手中没有牌所以无需考虑什么地方是正确的位置。如下图是一个插入排序的展示我们可以使用如下代码实现#include 一个算法最为重要的要求是正确性在正确性的前提下尽量降低时间复杂度和空间消耗。正确性分析通常来说一个值得我们研究的算法的核心部分是循环或者递归因为如果不包含循环和递归那么就意味着这个算法是线性的那么关于这个算法也就没有性能上的区别了那么就可以说这是一个不值得我们研究的算法为了能够论证这个算法的循环部分递归也是可以利用循环实现的是正确的我们通常会使用一种叫做循环不变式的概念。利用循环不变式论证算法的正确性主要分为三个步骤初始化循环的第一次迭代之前它为真。保持如果循环的某次迭代之前它为真那么下次迭代之前它仍为真。终止循环终止时不变式为我们提供了一个有用的性质该性质有助于证明此算法是正确的。看到这里相比很多读者已经意识到这就是数学中的“数学归纳法”。那么将这三步用于上文中的插入排序效果会是如何呢初始化在第一次迭代之前即当 i 1 时循环不变式成立因为子数组此时仅由1个元素组成即array[0]。此数组必然是有序的。保持当前 i 个元素组成的子数组已经有序后我们准备插入第 i1 个元素代码的第21-24行的部分保证了所有大于第 i1 个元素的数据均在此元素右方所有小于等于第 i1 个元素的数据均在此元素左方则当插入此元素后前 i1 个元素组成的子数组有序。终止循环终止的条件是 i array_length即前 array_length 个元素组成的子数组有序即整个数组有序。通过这三步分析我们证明了这个算法的正确性以后的文章我们提到的所有算法均可以通过此方法分析其正确性。虽然我们在后期可能会更加强调一个算法的运行效率对于一些显而易见的正确性可能会略过不讲但这并不意味着正确性分析不重要仅凭作者的经验来看很多学习算法的同学容易陷入一个怪圈只着眼于运行效率而忽略了算法本身正确性。运行效率分析对于一个算法的运行效率最直接的判断方式是将其写为一个程序并运行测速。但在大部分情况下这是不合理的。例如同一个算法由不同的程序员编写用不同的语言编写用不同的运行环境来测试或者用不同的硬件设备来运行都会有着巨大的差异如果有的算法非常复杂或者数据量很大需要几个小时甚至几天才能运行完成我们需要一直等它运行完成才能评判这个算法的运行效率吗显然用实际运行并计时的方式来评判一个算法的运行效率在大部分情况下是不合理的。对此我们引入了一种思想模型——随机访问机RAM来评估一个算法的运行效率。RAM模型包含真实计算机中常见的指令算术指令如加法减法乘法除法取余、向下取整向上取整数据移动指令装入、存储、复制和控制指令条件跳转无条件跳转子程序调用与返回上述这些指令所需时间均为常量即这些指令运行时间不变。同时在实际中计算机包含多级存储但为了简化问题我们一般不考虑高速缓存虚拟内存等多级存储简化为只有硬盘与内存的区别。再说了现在技术变的这么快说不定以后就没cache了呢考虑啥呀真的是。这一段没有看懂不要急下面会举一个例子看了例子后相信大部分读者就能明白了。有了模型现在就需要考虑如何进行评估。对于一个算法输入规模能够很大程度的影响运行时间例如插入排序中对10个数进行排序和对10亿个数进行排序。对此我们引入了输入规模与运行时间的概念。输入规模输入规模很大程度上依赖于具体问题来进行分析。例如排序中输入规模一般认为是需要排序的数据个数如果分析两个整数相乘则输入规模一般认为是两个数的总位数如果需要研究图论问题那么输入规模一般认为是图中的顶点数与边数。什么是输入规模没有一个具体的规定但一般而言就是指这个影响这个算法运行时间的最重要的那一个属性这个需要读者们多学习积累经验才能迅速的分析出一个问题的关键所在。运行时间这个运行时间不是指实际运行时间而是在RAM模型中需要执行的基本操作步数。什么是基本操作步数也就是我们上文中提到的RAM模型中的常见指令运行一条指令就是一步。虽然不同指令的运行时间不同但他们之间的差异都是常量级的例如加法指令可能需要1ms运行完成乘法指令需要10ms运行完成他们的比例是1:10运行100条加法指令与运行100条乘法指令所需时间比例依然是1:10这个常数时间的差异在我们后面面对的动辄 指数级 差异的比较之下就可以忽略不计了。为什么我们会忽略运行时间的常数差异呢一个很简单的道理如果我们的计算规模很小例如排序十个数不同算法之间差距可能只有不到1ms这点时间与你点击运行电脑突然卡了一下等事情需要花费的时间相比简直微不足道甚至都没必要去优化算法了。而如果计算规模很大例如要排序全国人民的身份证号差一点的算法插入排序同学说的就是你别东张西望了可能需要几年而好一点的算法可能只需要几个小时不同算法之间的运行时间差异甚至是指数级的这一点常数差异真的没有什么影响除非两个指令之间运行时间比例能达到百万级之类的那你干脆把差距这么大的指令也当做算法来研究研究优化一下了吧。等学习深入以后读者们也会发现我们大部分时候只考虑运行时间与输入规模之间的关系如是指数关系还是线性关系等同时评价一个算法好不好大部分情况下也是考虑输入规模较大的时候的增长趋势。运行效率分析案例现在我们以上文中的插入排序代码为例进行一下运行效率的分析我们此次分析会将常数差异考虑进去以印证我们前文所说的当输入规模较大时常数差异不重要的结论。表格中 n 表示输入规模即array_length 表示执行while循环的次数由于 } 并不占用运行时间故运行一次所需代价为0。那么我们将上述所有运行时间相加所得结果为现在我们又面临一个新的问题对于同一规模的输入如果输入不同其运行时间也是不同的。例如在此例中如果输入的数组就是已经升序的那么化简一下可以将此记为即在插入排序的最好情况下最后的运行时间与输入规模之间是线性关系。如果输入的数组是降序的那么化简一下可以将此记为即在插入排序的最坏情况下最后的运行时间与输入规模之间是二次函数关系。运行效率分析总结在我们上面的例子中我们既研究了最佳情况也研究了最坏情况但一般而言实际中我们的分析主要在于最坏情况我们以后的文章也将会主要着眼于最坏情况的分析。对此我们有以下理由一个算法的最坏情况给出了任何输入的运行时间的一个上界我们可以保证该算法不需要更长的时间无需有更多担心。在实际中最坏情况经常出现例如我们编写一个网页用户登录时我们需要将登陆数据与数据库中的数据进行对比在很多时候由于用户的错误输入或者恶意输入数据库中是没有这条记录的所以需要检索整个数据库也就是最坏情况。我们不能让这个最坏情况太差因为如果只是让用户最快登陆时间从0.1秒增加到0.2秒是可以接受的但当一个用户错误登陆时需要所有用户一起卡一天建议以“蓄意破坏计算机信息系统罪”立即去公安机关自首或者直接击毙。一般而言平均情况与最坏情况差距不大可能只有一个常数的差异。如插入排序中如果插入第n个数时平均情况下是在第n/2个数时插入最坏情况是在第n个数插入只有一个2倍关系所以平均情况的运行时间只是将最坏情况的运行时间除以2而已依然是二次函数关系并没有本质上的区别。当然我觉得还有另外一个原因最坏情况很好算而平均情况很多时候真的很难算的为了一个只需要花5分钟写完的算法我花了10分钟去分析它的平均情况我也很难的好吧这么多时间我拿去拯救世界不香吗。增长量级虽然说我们可以具体计算出一个算法的最坏情况但也挺花时间的。同时我们也注意到对于一个二次函数关系当n足够大时只有二次项才是影响其大小的关键这也就引出了数学中的渐进分析的概念也就是我们的增长量级即大家常说的那个讨人厌的大O符号小O符号。具体含义我们将在下一篇文章中介绍在这里我们只需要先知道一个结论在实际的算法效率分析中我们真正感兴趣的是运行时间的增长率或者增长量级即公式中最为重要的项例如插入排序中的二次项。因为当n真的很大的时候低阶项相对来说不太重要而常数项在n逐渐变大的过程中也逐渐不太重要了在实际中我们往往只关心数量级例如百万级的数据亿级的数据在这种情况下常数项是1还是10就没有必要关心了毕竟这种时候它带来的影响连低阶项都比不上了结语这是算法与数据结构系列的第一篇文章下一章我将会以归并排序为例介绍时间复杂度的概念再后面就是具体的算法与数据结构的分析了从最基础的时间复杂度、空间复杂度开始一步一步深入比如搜索排序基本数据结构各种神奇的树图矩阵等等后面应该也会介绍一些动态规划字符串处理等常用算法以及一些简单的数论算法和数学知识吧。如果有兴趣的话我大家也可以关注我一波没有意外情况的话我应该可能或许说不定不会鸽吧。原文链接albertcode.infoalbertcode.info个人博客albert的个人网站 - bug工厂albertcode.info微信公众号AlbertCodeInfo
