中国农村建设网站首页,网页设计参考网站,网页版梦幻西游水晶宫攻略,做网站 空间学会了 Python 基础知识#xff0c;想进阶一下#xff0c;那就来点算法吧#xff01;毕竟编程语言只是工具#xff0c;结构算法才是灵魂。
新手如何入门 Python 算法#xff1f;
几位印度小哥在 GitHub 上建了一个各种 Python 算法的新手入门大全。从原理到代码#xf…学会了 Python 基础知识想进阶一下那就来点算法吧毕竟编程语言只是工具结构算法才是灵魂。
新手如何入门 Python 算法
几位印度小哥在 GitHub 上建了一个各种 Python 算法的新手入门大全。从原理到代码全都给你交代清楚了。为了让新手更加直观的理解有的部分还配了动图。 文章目录技术提升算法的代码实现算法原理排序算法拓扑搜索算法插值搜索快速选择算法禁忌搜索密码https://github.com/TheAlgorithms/Python
技术提升
技术要学会分享、交流不建议闭门造车。一个人走的很快、一堆人可以走的更远。
本文来自技术群粉丝的分享、推荐资料、代码、数据、技术交流提升均可加交流群获取群友已超过2000人添加时切记的备注方式为来源兴趣方向方便找到志同道合的朋友。 方式①、添加微信号pythoner666备注来自 CSDN python 方式②、微信搜索公众号Python学习与数据挖掘后台回复加群 这个项目主要包括两部分内容
一是各种算法的基本原理讲解二是各种算法的代码实现。
算法的代码实现
算法的代码实现给的资料也比较丰富除了算法基础原理部分的 Python 代码还有包括神经网络、机器学习、数学等等代码实现。 例如在神经网络部分给出了 BP 神经网络、卷积神经网络、全卷积神经网络以及感知机等。 卷积神经网络代码示例
代码以 Python 文件格式保存在 GitHub 上需要的同学可以自行保存下载。
https://github.com/TheAlgorithms/Python
算法原理
在算法原理部分主要介绍了排序算法、搜索算法、插值算法、跳跃搜索算法、快速选择算法、禁忌搜索算法、加密算法等。
当然除了文字解释之外还给出了帮助更好理解算法的相应资源链接包括维基百科、动画交互网站链接。
例如在一些算法部分中其给出的动画交互链接非常完美帮助理解算法的运行机制。 交互动画地址
https://www.toptal.com/developers/sorting-algorithms/bubble-sort
排序算法
冒泡排序 冒泡排序有时也被称做沉降排序是一种比较简单的排序算法。这种算法的实现是通过遍历要排序的列表把相邻两个不符合排列规则的数据项交换位置然后重复遍历列表直到不再出现需要交换的数据项。当没有数据项需要交换时则表明该列表已排序。
桶排序算法 桶排序(Bucket sort)或所谓的箱排序是一个排序算法工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序。
鸡尾酒排序 鸡尾酒排序也就是定向冒泡排序鸡尾酒搅拌排序搅拌排序也可以视作选择排序的一种变形涟漪排序来回排序或快乐小时排序都是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
译者注
鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的性能原因是冒泡排序只从一个方向进行比对由低到高每次循环只移动一个项目。
以序列(2,3,4,5,1)为例鸡尾酒排序只需要访问一次序列就可以完成排序但如果使用冒泡排序则需要四次。但是在随机数序列的状态下鸡尾酒排序与冒泡排序的效率都很差劲。
插入排序 插入排序Insertion Sort是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。插入排序在实现上通常采用in-place排序的额外空间的排序因而在从后向前扫描过程中需要反复把已排序元素逐步向后挪位为最新元素提供插入空间。
归并排序 归并排序Merge sort或mergesort是创建在归并操作上的一种有效的排序算法效率为O(n log n)大O符号。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法Divide and Conquer的一个非常典型的应用且各层分治递归可以同时进行。
堆Heap 堆Heap是一种基于比较的排序算法。它可以被认为是一种改进的选择排序。它将其输入划分为已排序和未排序的区域并通过提取最大元素,将其移动到已排序区域来迭代缩小未排序区域。
译者注
Heap 始于 J._W._J._Williams 在1964 年发表的堆排序heap sort当时他提出了二叉堆树作为此算法的数据结构。
在队列中调度程序反复提取队列中第一个作业并运行因为实际情况中某些时间较短的任务将等待很长时间才能结束或者某些不短小但具有重要性的作业同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。
基数排序
基数排序Radix sort是一种非比较型整数排序算法其原理是将整数按位数切割成不同的数字然后按每个位数分别比较。由于整数也可以表达字符串比如名字或日期和特定格式的浮点数所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机Tabulation Machine上的贡献。
选择排序 选择排序Selection sort是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。
Shell排序 ShellSort是插入排序的一种推广允许交换相距很远的项。思路是安排元素列表以便从任何地方开始考虑到每个第n个元素都会给出一个排序列表。这样的列表叫做h排序。等效地可以被认为是h交错列表每个元素都是单独排序的。
拓扑
拓扑排序或有向图的拓扑排序是其顶点的线性排序使得对于从顶点u到顶点v的每个有向边uvu在排序中位于v之前。例如图的顶点可以表示要执行的任务并且边可以表示一个任务必须在另一个之前执行的约束在这个应用程序中拓扑排序只是任务的有效序列。当且仅当图形没有有向循环时即如果它是有向非循环图则拓扑排序是可能的DAG。任何DAG都具有至少一个拓扑排序并且已知算法用于在线性时间内构建任何DAG的拓扑排序。
时间复杂折线图
比较排序算法的复杂性冒泡排序插入排序选择排序 比较排序算法
Quicksort是一种非常快速的算法但实现起来相当棘手。Bubble sort是一种慢速算法但很容易实现。为了对小数据集进行排序冒泡排序可能是一个更好的选择。
搜索算法
线性搜索 线性搜索或顺序搜索是用于在列表中查找目标值的方法。它按顺序检查列表中的每个元素的目标值直到找到匹配或直到搜索完所有元素。
假设一个数组中有N个元素最好的情况就是要寻找的特定值就是数组里的第一个元素这样仅需要1次比较就可以。而最坏的情况是要寻找的特定值不在这个数组或者是数组里的最后一个元素这就需要进行N次比较。
Binary 二进制搜索 二进制搜索也称为半间隔搜索或对数搜索用于查找已排序数组中目标值的位置。它将目标值与数组的中间元素进行比较如果它们不相等则目标的一半被消除并且在剩下的一半上继续搜索直到成功。
插值搜索
插值搜索是一种用于搜索已按照键值的数值排序的数组中键的算法。
最先由WW Peterson在1957年描述。插值搜索类似于人们在电话目录中搜索名称的方法用于订购书籍条目的关键值在每个步骤中算法计算剩余搜索空间中的位置基于搜索空间边界处的键值和所寻找的键的值通常可以通过线性插值来寻找项目。
相比之下二进制搜索总是选择剩余搜索空间的中间丢弃一半或另一半这取决于在估计位置找到的密钥与所寻找的密钥之间的比较。剩余的搜索空间缩小到估计位置之前或之后的部分。线性搜索仅使用相等性因为它从一开始就逐个比较元素忽略任何排序。
平均插值搜索使得loglogn比较如果元素均匀分布其中n是要搜索的元素的数量。在最坏的情况下例如键的数值以指数方式增加它可以构成On比较。
在插值顺序搜索中插值用于查找正在搜索的项目附近的项目然后使用线性搜索来查找确切项目。
跳转搜索
跳转搜索是指有序列表的搜索算法。它首先检查所有项目的Lkm其中K∈N并且m是块大小直到找到大于搜索关键字的项目。为了在列表中找到搜索关键字的确切位置在子列表L[k-1mkm]上执行线性搜索。
m的最优值是√n其中n是列表L的长度。因为算法的两个步骤最多都是√n项所以算法在O√n时间内运行。这比线性搜索更好但比二分搜索差。优于后者的优点是跳转搜索只需要向后跳一次而二进制可以向后跳转到记录n次。
在最终执行线性搜索之前可以通过在子列表上执行多级跳转搜索来修改算法。对于k级跳跃搜索第l级的最佳块大小ml从1开始计数是nk1/k。修改后的算法将执行k个向后跳转并在Okn1/k 1时间内运行。
快速选择算法 快速选择Quicksort是一种从无序列表找到第k小元素的选择算法。它从原理上来说与快速排序有关。与快速排序一样都由托尼·霍尔提出的因而也被称为霍尔选择算法。同样地它在实际应用是一种高效的算法具有很好的平均时间复杂度然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。
快速选择的总体思路与快速排序一致选择一个元素作为基准来对元素进行分区将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是快速选择并不递归访问双边而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度从O(n log n)至O(n)不过最坏情况仍然是O(n2)。
禁忌搜索
禁忌搜索(Tabu Search,TS,又称禁忌搜寻法是一种现代启发式算法由美国科罗拉多大学教授Fred Glover在1986年左右提出的是一个用来跳脱局部最优解的搜索方法。其先创立一个初始化的方案基于此算法“移动”到一相邻的方案。经过许多连续的移动过程提高解的质量。
密码
凯撒密码
凯撒密码也称为凯撒密码移位密码凯撒代码或凯撒移位是最简单和最广为人知的加密技术之一。
它是一种替换密码其中明文中的每个字母都被字母表中的一些固定数量的位置的字母替换。例如左移3D将被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需要相同的算法因此可以使用相同的动作进行编码和解码。该算法几乎不提供加密安全性并且经常被引用为弱加密的典型示例。
