二进制搜索,也称为半间隔搜索或对数搜索,用于查找已排序数组中目标值的位置。它将目标值与数组的中间元素进行比较,如果它们不相等,则目标的一半被消除,并且在剩下的一半上继续搜索直到成功。
插值搜索
插值搜索是一种用于搜索已按照键值的数值排序的数组中键的算法。
最先由WW Peterson在1957年描述。插值搜索类似于人们在电话目录中搜索名称的方法(用于订购书籍条目的关键值):在每个步骤中,算法计算剩余搜索空间中的位置,基于搜索空间边界处的键值和所寻找的键的值,通常可以通过线性插值来寻找项目。
相比之下,二进制搜索总是选择剩余搜索空间的中间,丢弃一半或另一半,这取决于在估计位置找到的密钥与所寻找的密钥之间的比较。剩余的搜索空间缩小到估计位置之前或之后的部分。线性搜索仅使用相等性,因为它从一开始就逐个比较元素,忽略任何排序。
平均插值搜索使得log(log(n))比较(如果元素均匀分布),其中n是要搜索的元素的数量。在最坏的情况下(例如,键的数值以指数方式增加),它可以构成O(n)比较。
在插值顺序搜索中,插值用于查找正在搜索的项目附近的项目,然后使用线性搜索来查找确切项目。
跳转搜索
跳转搜索是指有序列表的搜索算法。它首先检查所有项目的Lkm,其中K∈N,并且m是块大小,直到找到大于搜索关键字的项目。为了在列表中找到搜索关键字的确切位置,在子列表L[(k-1)m,km]上执行线性搜索。
m的最优值是√n,其中n是列表L的长度。因为算法的两个步骤最多都是√n项,所以算法在O(√n)时间内运行。这比线性搜索更好,但比二分搜索差。优于后者的优点是跳转搜索只需要向后跳一次,而二进制可以向后跳转到记录n次。
在最终执行线性搜索之前,可以通过在子列表上执行多级跳转搜索来修改算法。对于k级跳跃搜索,第l级的最佳块大小ml(从1开始计数)是n(k1)/k。修改后的算法将执行k个向后跳转并在O(kn1/(k 1))时间内运行。
快速选择算法
快速选择(Quicksort)是一种从无序列表找到第k小元素的选择算法。它从原理上来说与快速排序有关。与快速排序一样都由托尼·霍尔提出的,因而也被称为霍尔选择算法。同样地,它在实际应用是一种高效的算法,具有很好的平均时间复杂度,然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。
快速选择的总体思路与快速排序一致,选择一个元素作为基准来对元素进行分区,将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是,快速选择并不递归访问双边,而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度,从O(n log n)至O(n),不过最坏情况仍然是O(n2)。
禁忌搜索
禁忌搜索(Tabu Search,TS,又称禁忌搜寻法)是一种现代启发式算法,由美国科罗拉多大学教授Fred Glover在1986年左右提出的,是一个用来跳脱局部最优解的搜索方法。其先创立一个初始化的方案;基于此,算法“移动”到一相邻的方案。经过许多连续的移动过程,提高解的质量。
密码
凯撒密码
凯撒密码,也称为凯撒密码,移位密码,凯撒代码或凯撒移位,是最简单和最广为人知的加密技术之一。
它是一种替换密码,其中明文中的每个字母都被字母表中的一些固定数量的位置的字母替换。例如,左移3,D将被A替换,E将变为B,依此类推。
该方法以Julius Caesar的名字命名,最初是他在私人通信中使用了它。由Caesar密码执行的加密步骤通常作为更复杂的方案的一部分,例如Vigenère密码,并且仍然在ROT13系统中具有现代应用。与所有单字母替换密码一样,Caesar密码很容易破解,在现代实践中基本上没有通信安全性。
Vigenère密码
Vigenère密码是一种通过使用基于关键字字母的一系列交织的凯撒密码来加密字母文本的方法。它是一种多字母替代形式。
Vigenère密码该方法最初由Giovan Battista Bellaso在其1553年的书“La cifra del”中提出。然而,该计划后来在19世纪被误用于BlaisedeVigenère,现在被广泛称为“Vigenère密码”。
虽然该密码易于理解和实施,但三个世纪以来它一直抵制所有打破密码的企图,因此也被称为这lechiffreindéchiffrable(法语为“难以理解的密码”)。Friedrich Kasiski是第一个在1863年发表破译Vigenère密码的通用方法。
转置密码
转置密码是一种加密方法,通过该加密方法,明文单元(通常是字符或字符组)所保持的位置根据常规系统移位,使得密文构成明文的排列。也就是说,单位的顺序改变(明文被重新排序)。
在数学上,双字符函数用于加密字符的位置和用于解密的反函数。
RSA (Rivest–Shamir–Adleman)
RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
1973年,在英国政府通讯总部工作的数学家克利福德·柯克斯(Clifford Cocks)在一个内部文件中提出了一个与之等效的算法,但该算法被列入机密,直到1997年才得到公开。
ROT13
ROT13(“旋转13个位置”,有时用连字符ROT-13)是一个简单的字母替换密码,用字母表后面的第13个字母替换一个字母。ROT13是古罗马开发的Caesar密码的特例。
因为基本拉丁字母中有26个字母(2×13),所以ROT13是自身的反转,也就是说,要撤消ROT13需要相同的算法,因此可以使用相同的动作进行编码和解码。该算法几乎不提供加密安全性,并且经常被引用为弱加密的典型示例。
Github地址:
https://github.com/TheAlgorithms/Python