网站设计欣赏国外,商城网站建设是 什么软件,外贸网站contact,福州建设网站的公司目录
一、顺序搜索
二、分析顺序搜索算法
三、二分搜索
四、分析二分搜索算法
五、散列
5.1 散列函数
5.2 处理冲突
5.3 实现映射抽象数据类型 搜索是指从元素集合中找到某个特定元素的算法过程。搜索过程通常返回True或False#xff0c;分别表示元素是否存在。有时分别表示元素是否存在。有时可以修改搜索过程使其返回目标元素的位置。
Python提供了运算符in通过它可以方便地检查元素是否在列表中。 15 in [3,5,2,4,1]
False3 in [3,5,2,4,1]
True
一、顺序搜索
存储在列表等集合中的数据项彼此存在线性或顺序关系每个数据项的位置与其他数据项相关。在Python列表中数据项的位置就是它的下标。因为下标是有序的所以能够顺序访问由此可以进行顺序搜索。
顺序搜索的原理从列表中的第一个元素开始沿着默认的顺序逐个查看直到找到目标元素或者查完列表。如果查完列表后仍没有找到目标元素则说明目标元素不在列表中。
无序列表的顺序搜索
def sequentialSearch(alist,item):pos0foundFalsewhile poslen(alist) and not found:if alist[pos]item:foundTrueelse:pospos1return found
二、分析顺序搜索算法
在无序列表中进行顺序搜索时的比较次数 最好情况最坏情况普通情况存在目标元素1nn/2不存在目标元素nnn
有序列表的顺序搜索
def orderedSequentialSearch(alist,item):pos0foundFalsestopFalsewhile poslen(alist) and not found and not stop:if alist[pos]item:foundTrueelse:if alist[pos]item:stopTrueelse:pospos1return found
只有当列表不存在目标元素时有序排列元素才会提高顺序搜索的效率。
在有序列表中进行顺序搜索时的比较次数 最好情况最坏情况普通情况存在目标元素1nn/2不存在目标元素1nn/2
三、二分搜索
在顺序搜索时如果第一个元素不是目标元素最多还要比较n-1次。但二分搜索不是从第一个元素开始搜索而是从中间的元素着手。如果这个元素是目标元素那就立即停止搜索如果不是则可以利用列表有序的特性排除一半的元素。如果目标元素比中间的元素大就可以直接排除列表左半部分和中间的元素。这是因为如果列表包含目标元素它必定位于右半部分。
有序列表的二分搜索
def binarySearch(alist,item):first0lastlen(alist)-1foundFalsewhile firstlast and not found:midpoint(firstlast)//2if alist[midpoint]item:foundTrueelse:if itemalist[midpoint]:lastmidpoint-1else:firstmidpoint1return found
这个算法是分治策略的好例子。分治是指将问题分解成小问题以某种方式解决小问题然后整合结果以解决最初的问题。对列表进行二分搜索时先查看中间的元素。如果目标元素小于中间的元素就只需要对列表的左半部分进行二分搜索。同理如果目标元素更大则只需对右半部分进行二分搜索。两种情况下都是针对一个更小的列表递归调用二分搜索函数。
二分搜索的递归版本
def binarySearch(alist,item):if len(alist)0:return Falseelse:midpointlen(alist)//2if alist[midpoint]item:return Trueelse:if itemalist[midpoint]:return binarySearch(alist[:midpoint],item)else:return binarySearch(alist[midpoint1:],item)
四、分析二分搜索算法
二分搜索算法的时间复杂度是O(logn)。
尽管二分搜索通常优于顺序搜索但当n较小时排序引起的额外开销可能并不划算。实际上应该始终考虑为了提高搜索效率额外排序是否值得。如果排序一次后能够搜索多次那么排序的开销不值一提。然而对于大型列表而言只排序一次也会有昂贵的计算成本因此从头进行顺序排序可能是更好的选择。
五、散列
通过散列可以构建一个时间复杂度为O(1)的数据结构。
散列表是元素集合其中的元素以一种便于查找的方式存储。散列表中的每个位置通常被称为槽其中可以存储一个元素。槽用一个从0开始的整数标记例如0号槽、1号槽、2号槽等等。初始情形下散列表中没有元素每个槽都是空的。可以用列表来实现散列表并将每个元素初始化为Python中的特殊值None。
散列函数将散列表中的元素与其所属位置对应起来。对散列表中的任一元素散列函数返回一个介于0和m-1之间的整数。首先来看第一个散列函数它有时被称作“取余函数”即用一个元素除以表的大小并将得到的余数作为散列值。取余函数是一个很常见的散列函数这是因为结果必须在槽编号范围内。
计算出散列值后就可以将每个元素插入到相应的位置。在11个槽中有六个被占用。占用率被称为载荷因子记作定义如下元素个数/散列表大小。
搜索目标元素时仅需使用散列函数计算出该元素的槽编号并查看对应的槽中是否有值。因为计算散列值并找到相应位置所需的时间是固定的所以搜索操作的时间复杂是O(1)。
如果两个元素的散列值相同散列函数会将两个元素都放入同一个槽这种情况叫作冲突也叫做“碰撞”。显然冲突给散列函数带来了问题。
5.1 散列函数
给定一个元素集合能将每个怨怒是映射到不同的槽这种散列函数称作完美散列函数。
我们的目标是创建这样一个散列函数冲突数最少计算方便元素均匀分布于散列表中。有多种常见的方法来扩展取余函数下面介绍其中的几种。
折叠法先将元素切成等长的部分最后一部分的长度可能不同然后将这些部分相加得到散列值。假设元素是电话号码436-555-4601以2位为一组进行切分得到43、65、55、46和01将这些数字相加后得到210.假设散列表有11个槽接着需要用210除以1并保留余数1所以电话号码436-555-4601被映射到散列表的1号槽。有些折叠法更进一步在加总前每隔一个数反转一次。就本例而言反转后的结果是4356556401219219%1110。
另一个构建散列函数的数学技巧是平方取中法先将元素取平方然后提取中间几位数。如果元素是44先计算44*441936然后提取中间两位93继续进行取余的步骤得到593%11。
我们也可以为基于字符的元素比如字符串创建散列函数。可以将单词cat看作序数值序列如下所示 ord(c)
99ord(a)
97ord(t)
116
因此可以将这些序数值相加并采用取余法得到散列值。
def hash(astring,tablesize):sum0for pos in range(len(astring)):sumsumord(astring[pos])return sum%tablesize
有趣的是针对异序词这个散列函数总是得到相同的散列值。要弥补这一点可以同字符位置作为权重因子。
def hash(astring,tablesize):sum0for pos in range(len(astring)):sumsumord(astring[pos])*(pos1)return sum%tablesize
5.2 处理冲突
当两个元素被分到同一个槽中时必须通过一种系统化方法在散列表中安置第二个元素。这个过程被称为处理冲突。
一种方法是在散列表中找到另一个空槽用于放置引起冲突的元素。简单的做法是从起初的散列值开始顺序遍历散列表知道找到一个空槽。注意为了遍历散列表可能需要往回检查第一个槽。这个过程被称为开放定址法它尝试在散列表中寻找下一个空槽或地址。由于是逐个访问槽因此这个做法被称作线性探测。
线性探测有个缺点那就是会使散列表中的元素出现聚集现象。也就是说如果一个槽发生太多冲突线性探测会填满附近的槽而这会影响后续插的元素。要避免元素聚集一种方法是扩展线性探测不再依次顺序查找空槽而是跳过一些槽这样做能使引起冲突的元素分布得更均匀。采用“加3”探测策略处理冲突后的元素是指发生冲突时为了找到空槽该策略每次跳两个槽。
再散列泛指在发生冲突后寻找另一个槽的过程。采用线性探测时再散列函数是newhashvaluerehash(oldhanshvalue)并且rehash(pos)(pos1)%sizeoftable。“加3”探测策略的再散列函数可以定义为rehash(pos)(pos3)%sizeoftable。也就是说可以将再散列函数定义为rehash(pos)(posskip)%sizeoftable。注意“跨步skip的大小要能够保证表中所有的槽最终都被访问到否则就会浪费槽资源。要保证这一点常常建议散列表的大小为素数。
平方探测是线性探测的一个变体它不采用固定的跨步而是通过再散列函数递增散列值。如果第一个散列值是h后续的散列值就是h1、h4、h9、h16等等。换句话说平方探测的跨步是一系列完全平方数。
另一种处理冲突的方法就是让每个槽有一个指向元素集合或链表的引用。链接法允许散列表中的同一个位置上存在多个元素。发生冲突时元素仍然被插入其散列值对应的槽中。不过随着同一个位置上的元素越来越多搜索变得越来越困难。
5.3 实现映射抽象数据类型
字典是最有用的Python集合之一。字典是存储键-值对的数据类型。键用来查找关联的值这个概念常常被称作映射。
映射抽象数据类型定义如下。它是将键和值关联起来的无序集合其中的键是不重复的键和值之间是一一对应的关系。映射支持以下操作。
Map()创建一个空的映射它返回一个空的映射集合。put(key,val)往映射中加入一个新的键值对。如果键已经存在就用新值替换旧值。get(key)返回key对应的值。如果key不存在则返回None。del通过del map[key]这样的语句从映射中删除键-值对。len()返回映射中存储的键-值对的数目。in通过key in map这样的语句在键存在时返回True否则返回False。
class HashTable:def __init__(self):self.size11self.slots[None]*self.sizeself.data[None]*self.sizedef put(self,key,data):hashvalueself.hashfunction(key,len(self.slots))if self.slots[hashvalue]None:self.slots[hashvalue]keyself.data[hashvalue]dataelse:if self.slots[hashvalue]key:self.data[hashvalue]data #替换else:nextslotself.rehash(hashvalue,len(self.slots))while self.slots[nextslot]!None and self.slots[nextslot]!key:nextslotself.rehash(nextslot,len(self.slots))if self.slots[nextslot]None:self.slots[nextslot]keyself.data[nextslot]dataelse:self.data[nextslot]data #替换def hashfunction(self,key,size):return key%sizedef rehash(self,oldhash,size):return (oldhash1)%sizedef get(self,key):startslotself.hashfunction(key,len(self.slots))dataNonestopFalsefoundFalsepositionstartslotwhile self.slots[position]!None and not found and not stop:if self.slots[position]key:foundTruedataself.data[position]else:positionself.rehash(position,len(self.slots))if positionstartslot:stopTruereturn datadef __getitem__(self, key):return self.get(key)def __setitem__(self, key, data):self.put(key,data)if __name____main__:HHashTable()H[54]catH[26]dogH[93]lionH[17]tigerH[77]birdH[31]cowH[44]goatH[55]pigH[20]chickenprint(H.slots)print(H.data)print(H[20])print(H[17])H[20]duckprint(H[20])print(H.data)print(H[99]) HashTable类的最后两个方法提供了额外的字典功能。我们重载__getitem__和__settiem__ 以通过[ ]进行访问。这意味着创建HashTable类之后就可以使用熟悉的索引运算符了。
