学习网

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 36866|回复: 0
收起左侧

高级语言程序设计(Python) - 哈尔滨工业大学-6.1.3 视频3

[复制链接]
发表于 1-25 20:22 | 显示全部楼层 |阅读模式
就可以介绍时间复杂度的概念所谓的时间复杂度它就是用来量化一个算法运行的时间那么这个时间呢和输入的长度成什么样的一个关系在表示时间复杂度的时候啊其实我们不需要显示的计算这些常数比如说k0k1那么也就是无论是可以k0为四还是k0为100的话时间复杂度都会随着输入的规模成正比我们用大o来表示这个时间复杂度他呢只保留高阶项比如4n+4高阶项呢就是这个n那么它的时间复杂度就是o(n)那即使变成137n加上其他的一个常数的话他的时间复杂度仍然是o(n)那如果n的平方加上三再加上四呢它的高阶项就是n的平方那么时间复杂度呢就是on的平方那么二的n次方再加上n的3次方这两个哪个是高级项呢显然二的n次方的阶更高最终呢时间复杂度呢就是二的n次方因此线性查找他的时间复杂度就是o(n)那么时间复杂度这种大o的表示能告诉我们什么呢他能告诉我们不过两个算法他的时间复杂度分别是o(n)和o n的平方我们都知道对于一个较大的输入a总是比算法b快那么如果算法a时间复杂度为on当规模翻倍的时候它的运行时间也会翻倍那如果算法a他的时间复杂度为on的平方如果输入规模翻倍的时候大家可以猜一下它的运行时间是不是也翻倍呢当然我们都知道不会是翻倍的因为n的平方如果变成2n的平方的话其实是变成四乘以n的平方所以说它的运行时间不是翻倍而是变成了原来的4倍那么大0不能告诉我们什么呢首先大n不能告诉我们这个程序实际的运行时间比如说10的100次方嗯但是时间复杂度是oo恩儿时的100次方n他的时间复杂度呢也是n那么这两个算法到底哪个快呢显然是下面这个更快但是从时间复杂度角度来看我们并不知道哪个更快第二个呢是大o也不能告诉我们规模较小输入的行为比如说恩的3次方但时间复杂度呢就是o n的3次10的6次方他并没有n那也就是说它的运行时间复杂度是一个常数时间显然长时间应该比上面的n的3次方更快但是当恩角小的时候啊10的6次方要明显的快于恩的3次方下面这条曲线就是不同的函数随着n的变化它的增长速度我们可以看到最快的就是这条绿色的直线他呢其实是一个常数时间也就是随着n的变化运行的时间呢仍然是不变的比如我们写一个函数无论输入的n是多少都返回一个常数比如说返回100那么即使n特别大它运行的时间也是非常快的那比常熟时间更慢的这条曲线呢就是log2n再慢一点呢就是这个线性的时间复杂度在慢的就是n乘以log2n那么n的平方呢就会慢得更多在慢的就是n的3次方x4次方等等当然二的n次方又会更慢我们实际来比较一下不同的函数他们实际的运行速度比如一个操作所需要时间是一微秒常数的时间复杂度无论输入规模如何变化他最终需要的时间都是一微秒那么logn的话那么当n为1400的时候结果呢就是10微妙而n呢就变成了1400微秒而n乘以log(n)就变成15毫秒而n平方就变成2000毫秒而n3次方呢最终需要56分钟可以看到不同时间复杂度那么随着n变大最终的实际运行时间差别是非常大的大家可以想一下如果要是n的4次方当输入规模变成1400的时候他的结果会是多少如果要是二的n次方呢之前我们介绍查找方法呢叫做线性查找当然它的时间复杂度是o(n)仍然会比较慢有没有更快的查找方法呢在这呢我们就介绍一种叫做二分查找的算法二分查找有一个限制他的收入不能是任意的一个列表而应该输入的是一个有序的列表比如说从小到大排序的一个列表那么返回的结果仍然是一样如果这个值在列表中则返回它相应的下标的位置如果不在的话则返回-1其实二分查找方法和我们之前介绍的用二分的方法求一个数它的平方根是非常类似的也就是我们首先猜我们要查找的数字如果我们要查找这个数字小于列表中中间这个元素那么就需要在这表中的前半部分查找就可以了如果要是大于列表中的中间这个元素呢就需要在这列表后半部分进行找当然最好的情况恰好是等于列表中的中间这个元素这时候就返回这个位置就可以了下面我们看一个实际的例子比如一个列表它的元素值分别是五十二十七等等我们要查找元素呢是44首先我们要查找整个这个列表它中间这个元素中间元素下标恰好是四那四呢它的值是38而我们要查找数字是44显然是大于38的这时候我们只需要在列表的右半部分继续查找就可以了而不需要再继续查找左半部分那么右半部分它的下标呢从五开始一直到八结束那么中间这个元素它的下标呢就是六而六呢是77,44又小于77那么就在他的左半部分继续查找就行这时候他的最左下标是5最右下标也是那么中间这元素仍然是恰好这个五呢结果就是44也就是我们找到了我们所要查找这个元素下标就是五好我们实际的来实现一下二分查找方法首先定义函数叫做bi_search()仍然有两个参数分别是lst和x我们需要两个变量low呢表示我们要查找的某一个子列表他的最左边的元素的下标但是初始化为零另外一个变量就是high他用来存储我们要查找的一个子序列他最右侧的这个元素的下标初始值呢就是恰好是len(lst-1)然后开始循环只要low小于等于high接下来我们就需要求中间这个元素的下标即mid他呢恰好等于low加上high然后再除以二然后呢就需要进行判断唉如果list[mid]等于x就是中间这个元素恰好和x相同这时候就会return mid如果中间这个元素如果大于x这时候就说明我们要查找元素在整个列表的左半部分所谓左半部分那就需要将high重新的置成lmid-1 ,else最后一种情况就是我们要查找这个元素大于中间这个元素那么这时候我们就需要将low设置成mid再加1如果这个循环啊都结束了仍然没有return的话这时我们就是return-1也是说明我们要查找元素并没有在列表中接下来我们就可以调用这个函数然后在list中查找仍然查找8还是list有一个条件他首先应该是一个有序的比如说按照从小到大顺序排列那么就不应该是十五八了说变成五八十十三那要查找元素呢是8他下标呢显然应该是一此时我们看一下返回结果是不是一呢唉恰好是一如果要查找的呢是十结果就是二如何查找是13呢应该是三但如果查找是15由于他不在列表中返回结果应该是-1看一下它结果恰好复一那如果要是七仍然也是-1那么二分查找他的时间复杂度应该是多少呢我们都知道每一次我们都是要查找这个元素的一半也就是当这个列表规模为n的时候我们只需要比较log以二为底的n这么多次就可以了那就是他的时间复杂度呢就是log以二为底的n那当n为100的时候线性查找呢一般要比较100次而这种二分查找最多比较7次可见他们差别是非常大的[此为课程内容大纲,相关资源下载地址请在论坛搜索标题名称]

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|小黑屋|学习资源网 ( 粤ICP备16100991号-2 )

GMT+8, 12-3 11:29 , Processed in 0.143233 second(s), 31 queries .

Powered by Discuz! X3.4 Licensed

© 2001-2017 Comsenz Inc. Template By ¡¾Î´À´¿Æ¼¼¡¿¡¾ www.wekei.cn ¡¿

快速回复 返回顶部 返回列表