算法_算法导论 - CSDN
算法 订阅
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法中的指令描述的是一个计算,当其运行时能从一个初始状态和(可能为空的)初始输入开始,经过一系列有限而清晰定义的状态,最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法,包含了一些随机输入。形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题,并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数,阿隆佐·邱奇于1936年提出的λ演算,1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前,依然常有直觉想法难以定义为形式化算法的情况。 展开全文
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法中的指令描述的是一个计算,当其运行时能从一个初始状态和(可能为空的)初始输入开始,经过一系列有限而清晰定义的状态,最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法,包含了一些随机输入。形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题,并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数,阿隆佐·邱奇于1936年提出的λ演算,1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前,依然常有直觉想法难以定义为形式化算法的情况。
信息
特    征
有穷性 确切性 输入 输出 可行
常    用
计算、数据处理和自动推理
外文名
Algorithm
中文名
算法
学    科
数学 计算机
算法特征
一个算法应该具有以下五个重要的特征:(Finiteness)算法的有穷性是指算法必须能在执行有限个步骤之后终止;(Definiteness)算法的每一步骤必须有确切的定义;(Input)一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件;(Output)一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;(Effectiveness)算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤,即每个计算步骤都可以在有限时间内完成(也称之为有效性)。
收起全文
精华内容
参与话题
  • 算法基础入门:90分钟搞定动态规划

    千人学习 2020-07-15 10:25:52
    为什么人人都要学算法? 程序员对算法通常怀有复杂情感,算法很重要是共识,但是否每个程序员都必须学算法是主要的分歧点。很多人觉得像人工智能、数据搜索与挖掘这样高薪的工作才用得上算法,觉得...
  • 【经典算法大全】收集51种经典算法 初学者必备

    万次阅读 多人点赞 2018-05-23 13:50:58
    《经典算法大全》是一款IOS平台的应用。里面收录了51种常用算法,都是一些基础问题。博主觊觎了好久,可悲哀的是博主没有苹果,所以从网上下了老奔的整理版并且每个都手敲了一遍。 虽然网上也有博客贴了出来,但是...

    《经典算法大全》是一款IOS平台的应用。里面收录了51种常用算法,都是一些基础问题。博主觊觎了好久,可悲哀的是博主没有苹果,所以从网上下了老奔的整理版并且每个都手敲了一遍。

    虽然网上也有博客贴了出来,但是自己写写感觉总是好的。现在分享个大家。

    代码和运行结果难免有出错的地方,请大家多多包涵。

     

    1.河内之塔(汉诺塔

    2.费式数列

    3.巴斯卡三角形

    4.三色棋

    5.老鼠走迷宫(1)

    6.老鼠走迷宫(2)

    7.骑士走棋盘

    8.八皇后

    9.八枚银币

    10.生命游戏

    11.字串核对

    12.双色河内塔三色河内塔

    13.背包问题 

    14.蒙地卡罗法求PI

    15.Eratosthenes筛选求质数

    16.超长整数运算(大数运算)  同时建议参考这篇文章:大数的四则运算-海子的博客园

    17.长PI

    18.最大公因数,最小公倍数,因式分解

    19.完美数

    20.阿姆斯壮数

    21.最大访客数

    22.中序转后序式(前序式  相关文章:中缀表达式值问题

    23.后序式运算 

    24.洗扑克牌(乱数排列)

    25.Craps赌博游戏

    26.约瑟夫问题

    27.排列组合   相关文章:母函数与排列组合

    28.格雷码(Gray Code)

    29.产生可能的集合  相关文章:集合划分问题

    30.m元素集合的n个元素子集

    31.数字拆解

    32.得分排行

    33.选择,插入,冒泡排序

    34.shell 排序法-改良的插入排序

    35.shaker排序法-改良的冒泡排序

    36.改良的选择排序

    37.快速排序法一

    38.快速排序法二

    39.快速排序法三

    40.合并排序法

    41.基数排序法

    42.循环搜寻法(使用卫兵)

    43.二分搜寻法(二分查找法,折半查找法)  相关文章:二分查找

    44.插补搜寻法

    45.费式搜寻法

    46.稀疏矩阵

    47.多维矩阵转一维矩阵

    48.上三角,下三角,对称矩阵

    49.奇数魔方阵

    50.4N魔方阵

    51.2(2N+1)魔方阵

     

    展开全文
  • 10大计算机经典算法

    万次阅读 多人点赞 2017-06-01 17:00:39
    算法一:快速排序法    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常...
    算法一:快速排序法                            

          快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

    快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

    算法步骤:                  

    1 .从数列中挑出一个元素,称为 “基准”(pivot),

    2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

    3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

       

    算法二:堆排序算法                            

     堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

    堆排序的平均时间复杂度为Ο(nlogn) 。

    算法步骤:

    1.创建一个堆H[0..n-1] 

    2.把堆首(最大值)和堆尾互换

    3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

    4. 重复步骤2,直到堆的尺寸为1

                               

    算法三:归并排序                            

     归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

    算法步骤:

    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置

    3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

    4. 重复步骤3直到某一指针达到序列尾

    5. 将另一序列剩下的所有元素直接复制到合并序列尾

                              

    算法四:二分查找算法                            

       二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半,时间复杂度为Ο(logn) 。                            

    算法五:BFPRT(线性查找算法)                            

     BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,依然能达到o(n)的时间复杂度,五位算法作者做了精妙的处理。

    算法步骤:

    1. 将n个元素每5个一组,分成n/5(上界)组。

    2. 取出每一组的中位数,任意排序方法,比如**排序。

    3. 递归的调用selection算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。

    4. 用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。

    5. 若i==k,返回x;若i<k,在小于x的元素中递归查找第i小的元素;若i>k,在大于x的元素中递归查找第i-k小的元素。

    终止条件:n=1时,返回的即是i小元素。                          

    算法六:DFS(深度优先搜索)                            

     深度优先搜索算法(Depth-First-Search),是搜索算法的一种。它沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。

    深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。


    深度优先遍历图算法步骤:

    1. 访问顶点v;

    2. 依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;

    3. 若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。

    上述描述可能比较抽象,举个实例:

    DFS 在访问图中某一起始顶点 v 后,由 v 出发,访问它的任一邻接顶点 w1;再从 w1 出发,访问与 w1邻 接但还没有访问过的顶点 w2;然后再从 w2 出发,进行类似的访问,… 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。

    接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。                            

    算法七:BFS(广度优先搜索)                            

      广度优先搜索算法(Breadth-First-Search),是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问,则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

    算法步骤:

    1. 首先将根节点放入队列中。

    2. 从队列中取出第一个节点,并检验它是否为目标。

    • 如果找到目标,则结束搜寻并回传结果。

    • 否则将它所有尚未检验过的直接子节点加入队列中。

    3. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

    4. 重复步骤2。

                               

    算法八:Dijkstra算法                            

     戴克斯特拉算法(Dijkstra’s algorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

    该算法的输入包含了一个有权重的有向图 G,以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边,都是两个顶点所形成的有序元素对。(uv) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合,而边的权重则由权重函数 wE → [0, ∞] 定义。因此,w(uv) 就是从顶点 u 到顶点 v 的非负权重(weight)。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重,就是该路径上所有边的权重总和。已知有 V 中有顶点 s 及 t,Dijkstra 算法可以找到 s 到 t的最低权重路径(例如,最短路径)。这个算法也可以在一个图中,找到从一个顶点 s 到任何其他顶点的最短路径。对于不含负权的有向图,Dijkstra算法是目前已知的最快的单源最短路径算法。

    算法步骤:

    1. 初始时令 S={V0},T={其余顶点},T中顶点对应的距离值

    若存在<V0,Vi>,d(V0,Vi)为<V0,Vi>弧上的权值

    若不存在<V0,Vi>,d(V0,Vi)为∞

    2. 从T中选取一个其距离值为最小的顶点W且不在S中,加入S

    3. 对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值缩短,则修改此距离值

    重复上述步骤2、3,直到S中包含所有顶点,即W=Vi为止

                           

    算法九:动态规划算法                            

     动态规划(Dynamic programming)是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

    动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量: 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

    关于动态规划最经典的问题当属背包问题。

    算法步骤:

    1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。

    2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。                            

    算法十:朴素贝叶斯分类算法                            

    朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理,就是在各种条件的存在不确定,仅知其出现概率的情况下,如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的,即假设样本每个特征与其他特征都不相关。

    朴素贝叶斯分类器依靠精确的自然概率模型,在有监督学**的样本集中能获取得非常好的分类效果。在许多实际应用中,朴素贝叶斯模型参数估计使用最大似然估计方法,换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。


    尽管是带着这些朴素思想和过于简单化的假设,但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。

    展开全文
  • 程序员必学的十个算法

    千次阅读 2018-06-22 10:36:32
    转载请在文章开头注明作者和出处作者: ChainGod(孙飞)原文链接: http://chaingod.io/article/14算法一:快速排序算法快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较...

    转载请在文章开头注明作者和出处

    作者: ChainGod(孙飞)

    原文链接: http://chaingod.io/article/14


    算法一:快速排序算法

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
    快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

    算法步骤:
    1 从数列中挑出一个元素,称为 “基准”(pivot),
    2 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
    3 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
    递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

    算法二:堆排序算法

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

    堆排序的平均时间复杂度为Ο(nlogn) 。
    算法步骤:
    创建一个堆H[0…n-1]
    把堆首(最大值)和堆尾互换
    3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
    4. 重复步骤2,直到堆的尺寸为1


    算法三:归并排序

    归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

    算法步骤:

    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置

    3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

    4. 重复步骤3直到某一指针达到序列尾

    5. 将另一序列剩下的所有元素直接复制到合并序列尾

    算法四:二分查找算法

    二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜 素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组 为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半,时间复杂度为Ο(logn) 。

    算法五:BFPRT(线性查找算法)

    BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分 析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,依然能达到o(n)的时间复杂 度,五位算法作者做了精妙的处理。

    算法步骤:

    1. 将n个元素每5个一组,分成n/5(上界)组。

    2. 取出每一组的中位数,任意排序方法,比如插入排序。

    3. 递归的调用selection算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。

    4. 用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。

    5. 若i==k,返回x;若i<k,在小于x的元素中递归查找第i小的元素;若i>k,在大于x的元素中递归查找第i-k小的元素。
      终止条件:n=1时,返回的即是i小元素。

    算法六:DFS(深度优先搜索)

    深度优先搜索算法(Depth-First-Search),是搜索算法的一种。它沿着树的深度遍历树的节点,尽可能深的搜索树的分 支。当节点v 的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发 现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。

    深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

    深度优先遍历图算法步骤:

    1. 访问顶点v;

    2. 依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;

    3. 若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。
      上述描述可能比较抽象,举个实例:
      DFS 在访问图中某一起始顶点 v 后,由 v 出发,访问它的任一邻接顶点 w1;再从 w1 出发,访问与 w1邻 接但还没有访问过的顶点 w2;然后再从 w2 出发,进行类似的访问,… 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。
      接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。

    算法七:BFS(广度优先搜索)

    广度优先搜索算法(Breadth-First-Search),是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问,则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

    算法步骤:

    1. 首先将根节点放入队列中。

    2. 从队列中取出第一个节点,并检验它是否为目标。
      如果找到目标,则结束搜寻并回传结果。
      否则将它所有尚未检验过的直接子节点加入队列中。

    3. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

    4. 重复步骤2。


    算法八:Dijkstra算法

    戴克斯特拉算法(Dijkstra’s algorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

    该算法的输入包含了一个有权重的有向图 G,以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边,都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合,而边的权重则由权重函数 w: E [0, ∞] 定义。因此,w(u, v) 就是从顶点 u 到顶点 v 的非负权重(weight)。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重,就是该路径上所有边的权重总和。已知有 V 中有顶点 s 及 t,Dijkstra 算法可以找到 s 到 t的最低权重路径(例如,最短路径)。这个算法也可以在一个图中,找到从一个顶点 s 到任何其他顶点的最短路径。对于不含负权的有向图,Dijkstra算法是目前已知的最快的单源最短路径算法。

    算法步骤:

    1. 初始时令 S={V0},T={其余顶点},T中顶点对应的距离值
      若存在<v0,vi>,d(V0,Vi)为<v0,vi>弧上的权值
      若不存在<v0,vi>,d(V0,Vi)为∞

    2. 从T中选取一个其距离值为最小的顶点W且不在S中,加入S

    3. 对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值缩短,则修改此距离值
      重复上述步骤2、3,直到S中包含所有顶点,即W=Vi为止

    算法九:动态规划算法

    动态规划(Dynamic programming)是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

    动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 通常许多 子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量: 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个 子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

    关于动态规划最经典的问题当属背包问题。

    算法步骤:

    1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。

    2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。 动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是 在表格中简单地查看一下结果,从而获得较高的效率。

    算法十:朴素贝叶斯分类算法

    朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理,就是在各种条件的存在不确定,仅知其出现概率的情况下, 如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的,即假设样本每个特征与其他特征都不相关。
    朴素贝叶斯分类器依靠精确的自然概率模型,在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中,朴素贝叶斯模型参数估计使用最大似然估计方法,换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。


    作者:
    链接:https://www.imooc.com/article/31122
    来源:慕课网
    展开全文
  • Java经典算法讲解

    万人学习 2019-06-24 11:57:47
    在面试中,算法题目是必须的,通过算法能够看出一个程序员的编程思维,考察对复杂问题的设计与分析能力,对问题的严谨性都能够体现出来。一个算法的好坏,直接影响一个方法调用的性能,进而影响软件的整体性能。算法...
  • 面试题20. 表示数值的字符串 本题的题目描述比较简单,例子比较少,解法也有多种,比如DFA确定有限状态机(然鹅我不会,回头再去了解了解),那咋办呢,有个投机取巧的方法就是正则表达式匹配直接调用库函数,那就...

    面试题20. 表示数值的字符串

    在这里插入图片描述
    本题的题目描述比较简单,例子比较少,解法也有多种,比如DFA确定有限状态机(然鹅我不会,回头再去了解了解),那咋办呢,有个投机取巧的方法就是正则表达式匹配直接调用库函数,那就不说了。正常的解法那就按照题目的意思和规则办,有啥情况就分析啥情况,走一步看一步就完事。
    代码如下(思路在注释):

    class Solution {
    public:
        bool isNumber(string s) {
            if(s.empty() || s==" ") return false;
            int l =s.find_first_not_of(' ');//去掉前边的空格
            int start = l;
            int r =s.find_last_not_of(' ');//去掉后边的空格
            bool numflag = false;//数值标记
            bool eflag = false;//指数标记
            bool dotflag = false;//点标记
            for(;l<=r; ++l)
            {
                if(isdigit(s[l]))
                    numflag = true;
                else if(s[l]=='.')
                {
                    //.之前不能出现e或者.
                    if(dotflag || eflag)
                        return false;
                    dotflag = true;
                }else if(s[l]=='e' || s[l]=='E')
                {
                    //E之前不能出现E,且必须有数字
                    if(eflag || !numflag)
                        return false;
                    eflag = true;
                    numflag = false;//重置数字标志
                }else if(s[l]=='+' || s[l]=='-')
                {
                    //+-号必须在第一个位置或者在E之后的第一个位置
                    if(l!=start && s[l-1]!='e' && s[l-1]!='E')
                        return false;
                }else
                    //其余不合法字符
                    return false;
            }
            return numflag;
        }
    };
    

    面试题21. 调整数组顺序使奇数位于偶数前面

    在这里插入图片描述
    解法1:双指针

    class Solution {
    public:
        vector<int> exchange(vector<int>& nums) {
            //双指针法
            int lo = 0, hi = nums.size()-1;
            while(lo<hi)
            {
                while(lo<hi && (nums[lo]&1))
                    ++lo;
                while(lo<hi && (nums[hi]&1)==0)
                    --hi;
                swap(nums[lo],nums[hi]);
            }
            return nums;
        }
    };
    

    解法2:快慢指针

    class Solution {
    public:
        vector<int> exchange(vector<int>& nums) {
            //快慢指针
            int slow = 0, fast = 0;
            while(fast<nums.size())
            {
                if(nums[fast]&1)
                    swap(nums[slow++],nums[fast]);
                ++fast;
            }
            return nums;
        }
    };
    

    面试题22. 链表中倒数第k个节点

    在这里插入图片描述
    思路:1、最直接的想法肯定是遍历一遍链表,然后统计节点个数n,然后从头节点开始顺序遍历,向前进n-k个节点,即到达倒数第k个节点,这样的情况下需要顺序遍历两次链表,因此时间复杂度有O(n^2),效率是较低的;2、链表的遍历思想中很容易想到一种思路,即双指针或者是快慢指针,本题可以引用双指针,初始化两个指针起始都指向头指针,然后指针p2先走k步,然后p1,p2在同时前进直到p2到达链表尾端,此时p1即倒数第k个节点,这样实际上只需要遍历一遍链表,即p2从头走到了尾,因此时间复杂度降低到O(n)。

    class Solution {
    public:
        ListNode* getKthFromEnd(ListNode* head, int k) {
            auto p1 = head;
            auto p2 = head;
            while(k--)
            {
                p2 = p2->next;
            }
            while(p2)
            {
                p2=p2->next;
                p1=p1->next;
            }
            return p1;
        }
    };
    

    面试题24. 反转链表在这里插入图片描述

    解法1:递归

    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            //递归法
            if(!head || !head->next) return head;
            ListNode* newhead = reverseList(head->next);
            head->next->next = head;
            head->next = nullptr;
            return newhead;
        }
    };
    

    解法2:双指针

    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            //双指针
            ListNode* pre = nullptr, *cur = head;
            while(cur)
            {
                auto post = cur->next;
                cur->next = pre;
                pre = cur;
                cur = post;
            }
            return pre;
        }
    };
    

    面试题25. 合并两个排序的链表在这里插入图片描述

    思路:整体思想和归并排序一样,定义一个伪头部dummy_head与一定前驱节点pre,然后对l1和l2两个链表进行遍历归并,直至某一链表值为空,最后再将非空的链表接上即可。

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            //伪头结点法
            ListNode* dummy_head = new ListNode(-1);
            auto pre = dummy_head;
            while(l1 && l2)
            {
                if(l1->val<=l2->val)
                {
                    pre->next = l1;
                    pre = l1;
                    l1 = l1->next;
                }else
                {
                    pre->next = l2;
                    pre = l2;
                    l2 = l2->next;
                }
            }
            if(!l1) pre->next = l2;
            else pre->next = l1;
            return dummy_head->next;
        }
    };
    

    面试题26. 树的子结构

    在这里插入图片描述
    解题思路:递归求解,1、定义一个辅助函数helper(),去判断两棵树是否相等;2、对树A进行遍历 ,以每一个节点为根节点的树与树B是否相等,如果存在相等,即B为A的子树。
    代码如下:

    class Solution {
    public:
        bool isSubStructure(TreeNode* A, TreeNode* B) {
            //递归
            if(!B || !A) return false;
            if(A->val==B->val)
                if(helper(A,B)) return true;
            return isSubStructure(A->left,B) || isSubStructure(A->right,B);
        }
    private:
        bool helper(TreeNode* A, TreeNode* B)
        {
            if(!B) return true;
            if(!A && B) return false;
            if(A->val!=B->val) return false;
            return helper(A->left,B->left) && helper(A->right,B->right);
        }
    };
    

    面试题27. 二叉树的镜像(翻转二叉树)

    在这里插入图片描述
    解法1:递归

    class Solution {
    public:
        TreeNode* mirrorTree(TreeNode* root) {
            //递归法
            if(!root) return root;
            auto left = mirrorTree(root->left);
            auto right = mirrorTree(root->right);
            root->left = right;
            root->right = left;
            return root;
        }
    };
    

    解法2:辅助队列

    class Solution {
    public:
        TreeNode* mirrorTree(TreeNode* root) {
            //队列
            if(!root) return root;
            queue<TreeNode*> q;
            q.push(root);
            while(!q.empty())
            {
                auto cur = q.front();
                q.pop();
                auto tmp = cur->left;
                cur->left = cur->right;
                cur->right = tmp;
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            return root;
        }
    };
    

    今日刷题笔记顺利完成,今日更多的题目是关于链表与树的内容,因此有许多的递归应用。同时也能感觉到链表中常用的方法:双指针可以优化链表的遍历或操作。明日继续!!!

    展开全文
  • 新的一天,新的开始!!! 面试题15.... 思路:本题主要考察的是一个位运算。主要解题思路有两种:1、位与&运算,对于n&1如果为1,即末位是1,否则为0,借助这个思路,可以对n的没一位,按位与1进行判断,为1则...
  • 面试题38. 字符串的排列 方法1;交换回溯法(时间消耗比较爆炸) class Solution { public: vector<string> permutation(string s) { //交换回溯法 backtrack(s,0);... void backtrack(string s,int idx)
  • 算法的世界是真的奇妙,有趣,深深不能自拔!!!前段时间刚学习算法与数据结构的时候都是一脸懵逼,看啥啥不懂,软磨硬泡了两个月,leetcode也刷了两三百题了,剑指Offer也过了一遍,今日起再刷第二遍,同时也对...
  • 剑指offer刷题笔记

    2020-04-26 21:48:01
    一个相当惨烈的开始f 一、数组: 题目:在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数...
  • 大神的算法学习之路

    万次阅读 多人点赞 2018-10-29 18:30:58
    严格来说,本文题目应该是我的数据结构和算法学习之路,但这个写法实在太绕口——况且CS中的算法往往暗指数据结构和算法(例如算法导论指的实际上是数据结构和算法导论),所以我认为本文题目是合理的。 原文链接:...
  • 什么是算法

    万次阅读 多人点赞 2016-12-14 10:56:36
    什么是算法 1、什么是算法 算法(algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。 mark:我们...
  • A*算法

    千次阅读 2019-07-25 19:34:03
    A*算法 注: 讲解部分来自博客园 Nickname:XXX已失联 作者博客:https://www.cnblogs.com/21207-iHome 原文章:https://www.cnblogs.com/21207-iHome/p/6048969.html Dijkstra算法 迪杰斯特拉(Dijkstra)算法是...
  • 五大常用算法

    万次阅读 2017-01-12 16:19:57
    五大常用算法
  • 遗传算法适合求解离散问题,具备数学理论支持,但是存在着汉明悬崖等问题.粒子群算法适合求解实数问题,算法简单,计算方便,求解速度快,但是存在着陷入局部最优等问题.蚁群算法适合在图上搜索路径问题,计算开销会大.要将...
  • 智能优化算法简介

    万次阅读 2019-06-05 21:40:36
    智能优化算法: 受人类智能、生物群体社会性或自然现象规律的启发。 主要包括: (1)遗传算法: 模仿自然界生物进化机制 (2)差分进化算法: 通过群体个体间的合作与竞争来优化搜索 (3)免疫算法: 模拟生物免疫系统学习和...
  • Floyd算法详解——包括解题步骤与编程

    万次阅读 多人点赞 2020-04-01 10:30:15
    一、Floyd算法原理 Floyd算法是一个经典的动态规划算法,它又被称为插点法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。Floyd算法是一种利用动态规划的思想...
  • 算法的五大特性

    万次阅读 2018-08-14 10:27:07
    算法一定是为了解决某一个问题产生。一定是可以解决问题的。空谈算法没有意义。 算法的五大特性: 输入: 算法具有0个或多个输入 输出: 算法至少有1个或多个输出 有穷性: 算法在有限的步骤之后会自动结束而不会...
  • 算法图解》高清PDF版

    万次阅读 热门讨论 2017-05-14 22:03:27
    算法图解》高清PDF版,像小说一样好看容易理解的算法书籍,适合算法和竞赛入门者学习,书中的示例代码是python。
  • 经典算法书籍推荐以及算法书排行【算法四库全书】 作者:霞落满天 https://linuxstyle.blog.csdn.net/ https://blog.csdn.net/21aspnet 行文方式:类似《四库全书》截取经典算法书目录和精华篇章 版权说明:本文...
1 2 3 4 5 ... 20
收藏数 3,301,611
精华内容 1,320,644
关键字:

算法