查找
线性(顺序)关系:数据项保存在列表这样的集合中。
- 顺序查找:按照顺序来访问和查找数据项;针对无序表当所要找的数据不在表中时查找需要遍历整个列表,而对于有序表可以设置一个提前结束标志减少计算量。但无论是有序表还是无序表其算法复杂度都为O(n)。
-
二分查找(binary search):对于有序表可以从中间项开始匹配,不断缩小表的规模知道找到数据的位置。二分查找法也体现了分治算法。因此二分查找法可以用递归实现。算法复杂度为O(log n)。
def binarySearch(alist,item): #二分查找的递归实现 ...... midpoint = len(alist)//2 if alist[midpoint]==item: return True else: #减小规模,调用自身 if item
对于两种查找算法,需要根据实际的应用情况进行选择。
排序
-
冒泡排序(bubble sort):两两相邻的数据进行比较,多趟之后即可完成排序。与在c语言中交换两个位置的值需要中间变量不同,python中可以使用
语句完成。算法每趟的比较次数由n-1不断递减,因此算法复杂度为O(n^2)。alist[i],alist[i+1]=alist[i+1],alist[i]
冒泡排序常作为其他算法的对比基准(妥妥的工具人🙃),其中的对次比对交换操作时无效的。优势在于无需额外储存空间的开销。
改进的冒泡排序:当某次比对未发生交换,便说明比对完成,可以提前结束。def shortBubbleSort(alist): ...... exchange = False for i in range(passnum): if alist[i]>alist[i+1]: exchange = True alist[i],alist[i+1]=alist[i+1],alist[i] passnum = passnum-1
-
选择排序(Selection Sort):对冒泡算法中,每趟只进行一次交换。先记录最大项所在的位置再交换。
-
插入排序(Insertion Sort):复杂度仍为O(n^2);是中唯持一个已排好序的子列表,其位置始终在列表的前部。并将其逐步扩大只全表。列表越接近有序,插入排序的对比次数就越少。
def insertionSort(alist): ...... while position > 0 and alist[position-1]>currentvalue: alist[position]=alist[position-1] position = position - 1 #每次与左侧的项进行比较,如果左侧的值大就将其右移,依次循环直到左侧值更小,在之前的空位中插入。 alist[position]=currentvalue
-
谢尔排序(Shell Sort):以“间隔”划分子列表,每个子列表执行插入排序,从而减少整体排序对比的次数。最后再进行标准的插入排序。减少了插入排序中无效的比对,介于O(n)于O(n^2)之间。
分治思想的排序算法
-
归并排序(Merge Sort):不断将数据表分裂为原来的一半,直到表中仅有一个数据项。之后再从最小规模开始排序(两个列表中小的先放,迭代,最后归并剩余项)直到完成这个列表的排序。
总体来说分为分裂和归并两个过程,算法复杂度分别为O(log n)和O(n)。但会占用更多的储存空间。
-
快速排序(Quick Sort):依据“中值”将数据项分为两半,排序。不断分解至仅有一个数据项。算法复杂度取决于“中值”选取的情况,综合为O(log n),但不需要额外的储存空间。“中值”选取中很难取得列表中准确的中值(真要准确的中值不还得排序😐),因此只能尽可能通过各种方法使选取的值与“中值”接近。
分裂方法:左标向右移动,直到遇到比中值大的左标;同时右标向右移动,直到遇到比中值小的。将左右标指向的值交换并继续向前移动。当左标到达右标的右侧,右标所指位置即为“中值”。
散列(Hashing)
散列可以使查找算法的复杂度降到O(1),散列表(hash table)包含用来储存数据的槽(slot)以及槽对应的唯一的名称。槽被数据项占据的比例称为负载因子。
数据与槽名称通过散列函数来对应。可以通过除余数来实现槽号与槽数据项的对应,但当要存储的两个数字余数相同时便会产生冲突。
如果一个散列函数能不会造成冲突便称之为完美散列函数。完美散列函数可以用于数据校验。将散列值看作槽中信息的摘要,由于该摘要具有唯一性因此可以通过摘要对比信息的异同。要具备数据校验的函数应具有以下特性;压缩性、易计算性、抗修改性和抗冲突性。
近似完美散列函数MD5,SHA。
区块链
区块链是一种分布式数据库,具有去中心化的特点。区块链由区块(block)组成。每个区块中包含着头(head)和体(body)。头中记录着一些元数据和链接到前一个区块的信息(生成时间、前一个区块的散列值)。
区块链具有不可修改性。由于区块链的分布式的性质,同步速度较慢因此新区快的添加速度被限制。
PS:每次虚拟货币涨的时候,硬件价格便会水涨船高,加上黄牛党的推波助澜,DIY玩家苦不堪言。
散列函数的设计
- 折叠法:对数据分段、相加、求余得到槽号。通过哥数反转的方法进行微调。
- 平方取中法:数据平方、取中间两位、求余(相比折叠法,计算量提高)。
特殊情况
- 对于非数项可通过ASCⅡ表进行转换。
- 对于变为词,加入权重因子
散列函数在设计时盈尽量简单并减少冲突。
冲突解决方案
再找一个空槽放置冲突数据(开放定址、再散列)。
- 线性探测:向后逐个寻找空槽,查找时顺序查找。缺点:有聚集趋势。
- 跳跃式探测;选择固定步长或逐步变化进行探测。固定步长取值时不能被散列表大小整除,否则会产生周期。
数据项链:槽扩展为容纳数据项的集合。这会延长查找的时间