精华内容
下载资源
问答
  • 五种常见的基本算法描述

    千次阅读 2020-04-18 17:25:22
    1.分治法 2.动态规划 3.贪心 4.回溯 5.分支限界法

    1.分治法

    分治法


    2.动态规划

    动归


    3.贪心

    贪心



    4.回溯

    回溯


    5.分支限界法

    分支限界

    展开全文
  • 《算法导论》常见算法总结

    万次阅读 多人点赞 2018-11-08 15:51:55
    调整过程如下图所示: 4、堆排序算法 堆排序算法过程为:先调用创建堆函数将输入数组A[1…n]造成一个最大堆,使得最大的值存放在数组第一个位置A[1],然后用数组最后一个位置元素与第一个位置进行交换,并将堆的大小...

    前言:本篇文章总结中用到很多其他博客内容,本来想附上原作链接,但很久了未找到,这里关于原创性均来源于原作者。

    分治法

    分治策略的思想:

    顾名思义,分治是将一个原始问题分解成多个子问题,而子问题的形式和原问题一样,只是规模更小而已,通过子问题的求解,原问题也就自然出来了。总结一下,大致可以分为这样的三步:

    分解:将原问题划分成形式相同的子问题,规模可以不等,对半或2/3对1/3的划分。
    解决:对于子问题的解决,很明显,采用的是递归求解的方式,如果子问题足够小了,就停止递归,直接求解。
    合并:将子问题的解合并成原问题的解。

    这里引出了一个如何求解子问题的问题,显然是采用递归调用栈的方式。因此,递归式与分治法是紧密相连的,使用递归式可以很自然地刻画分治法的运行时间。所以,如果你要问我分治与递归的关系,我会这样回答:分治依托于递归,分治是一种思想,而递归是一种手段,递归式可以刻画分治算法的时间复杂度。所以就引入本章的重点:如何解递归式?

    分治法适用的情况

    分治法所能解决的问题一般具有以下几个特征:

    1. 该问题的规模缩小到一定的程度就可以容易地解决
    2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
    3. 利用该问题分解出的子问题的解可以合并为该问题的解;
    4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

    第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;
    第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;、
    第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。
    第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

    ————————————————————————————————————————————

    最大堆最小堆

    1、堆

    堆给人的感觉是一个二叉树,但是其本质是一种数组对象,因为对堆进行操作的时候将堆视为一颗完全二叉树,树种每个节点与数组中的存放该节点值的那个元素对应。所以堆又称为二叉堆,堆与完全二叉树的对应关系如下图所示:

    通常给定节点i,可以根据其在数组中的位置求出该节点的父亲节点、左右孩子节点,这三个过程一般采用宏或者内联函数实现。书上介绍的时候,数组的下标是从1开始的,所有可到: PARENT(i)=i/2  LEFT(i) = 2i   RIGHT(i) = 2i+1
      
    根据节点数值满足的条件,可以将分为最大堆和最小堆。
    最大堆的特性是:除了根节点以外的每个节点i,有A[PARENT(i)] >= A[i],最小堆的特性是:除了根节点以外的每个节点i,有A[PARENT(i)] >=A[i]。
      
    把堆看成一个棵树,有如下的特性:

    (1)含有n个元素的堆的高度是lgn。
    (2)当用数组表示存储了n个元素的堆时,叶子节点的下标是n/2+1,n/2+2,……,n。
    (3)在最大堆中,最大元素该子树的根上;在最小堆中,最小元素在该子树的根上。

    2、保持堆的性质

    堆个关键操作过程是如何保持堆的特有性质,给定一个节点i,要保证以i为根的子树满足堆性质。书中以最大堆作为例子进行讲解,并给出了递归形式的保持最大堆性的操作过程MAX-HEAPIFY。先从看一个例子,操作过程如下图所示:

    从图中可以看出,在节点i=2时,不满足最大堆的要求,需要进行调整,选择节点2的左右孩子中最大一个进行交换,然后检查交换后的节点i=4是否满足最大堆的要求,从图看出不满足,接着进行调整,直到没有交换为止。

    3、建堆

    建立最大堆的过程是自底向上地调用最大堆调整程序将一个数组A[1…N]变成一个最大堆。将数组视为一颗完全二叉树,从其最后一个非叶子节点(n/2)开始调整。调整过程如下图所示:

    4、堆排序算法

    堆排序算法过程为:先调用创建堆函数将输入数组A[1…n]造成一个最大堆,使得最大的值存放在数组第一个位置A[1],然后用数组最后一个位置元素与第一个位置进行交换,并将堆的大小减少1,并调用最大堆调整函数从第一个位置调整最大堆。给出堆数组A={4,1,3,16,9,10,14,8,7}进行堆排序简单的过程如下:
    (1)创建最大堆,数组第一个元素最大,执行后结果下图:

    (2)进行循环,从length(a)到2,并不断的调整最大堆,给出一个简单过程如下:

    5、问题

    (1)在创建最大堆的过程中,为什么从最后一个非叶子节点(n/2)开始到第一个非叶子结束,而不是从第一个非叶子节点(1)到最后一个非叶子节点(n/2)结束呢?

    我的想法是:如果是从第一个非叶子节点开始创建堆,有可能导致创建的堆不满足堆的性质,使得第一个元素不是最大的。这样做只是使得该节点的和其左右孩子节点满足堆性质,不能确保整个树满足堆的性质。如果最大的节点在叶子节点,那么将可能不会出现在根节点中。例如下面的例子:

    从图中可以看出,从第一个非叶子节点开始创建最大堆,最后得到的结果并不是最大堆。而从最后一个非叶子节点开始创建堆时候,能够保证该节点的子树都满足堆的性质,从而自底向上进行调整堆,最终使得满足最大堆的性质。

    6、总结:

    1.调整最大堆的时间复杂度:O(lgn)

    2.建堆,由于每次比较的高度其实不大,所以对于一个无序的数组n,将其构造成为最大堆的时间复杂度是O(n),是一个线性的时间复杂度

    3.利用最大堆的方式去排序一个无序的数据,时间复杂度是O(n+n*lgn)=O(nlgn)

    4.对于最大堆建立的时候,需要主要的是,开始建立的时候都是从最后一个非叶子节点向上(数组向前)进行建立堆,这样做的目的是,可以让叶子节点的最大数据通过调整到根节点上。
    如果从第一个根节点开始建立堆的话,那么如果最大节点在叶子节点,这样调整将不能导致最大数据调整到根节点上,因为只能保证当前的节点和叶子节点的大小调整,调整完根节点这个节点,之后就没有调整了。

    ————————————————————————————————————————————

    优先队列

    队列是一种满足先进先出(FIFO)的数据结构,数据从队列头部取出,新的数据从队列尾部插入,数据之间是平等的,不存在优先级的。这个就类似于普通老百姓到火车站排队买票,先来的先买票,每个人之间是平等的,不存在优先的权利,整个过程是固定不变的。而优先级队列可以理解为在队列的基础上给每个数据赋一个权值,代表数据的优先级。与队列类似,优先级队列也是从头部取出数据,从尾部插入数据,但是这个过程根据数据的优先级而变化的,总是优先级高的先出来,所以不一定是先进先出的。这个过就类似于买火车票时候军人比普通人优先买,虽然军人来的晚,但是军人的优先级比普通人高,总是能够先买到票。通常优先级队列用在操作系统中的多任务调度,任务优先级越高,任务优先执行(类似于出队列),后来的任务如果优先级比以前的高,则需要调整该任务到合适的位置,以便于优先执行,整个过程总是使得队列中的任务的第一任务的优先级最高。

    优先级队列有两种:最大优先级队列和最小优先级队列,这两种类别分别可以用最大堆和最小堆实现。书中介绍了基于最大堆实现的最大优先级队列。一个最大优先级队列支持的操作如下操作:

    INSERT(S,x):把元素x插入到集合S
    MAXIMUM(S):返回S中具有最大关键字的元素
    EXTRACT_MAX(S):去掉并返回S中的具有最大关键字的元素
    INCREASE_KEY(S,x,k):将元素x的关键字的值增加到k,这里k值不能小于x的原关键字的值。

    问题

    如何使用优先级队列实现一个先进先出的队列和先进后出的栈?

    我的想法是:队列中的元素是先进先出(FIFO)的,因此可以借助最小优先级队列实现队列。具体思想是,给队列中的每个元素赋予一个权值,权值从第一个元素到最后一个依次递增(如果采用数组实现的话,可以用元素所在的下标作为优先级,优先级小的先出队列),元素出队列操作每次取优先级队列第一个元素,取完之后需要堆最小优先级队列进行调整,使得第一个元素的优先级最小。栈中的元素与队列刚好相反,元素是先进后出(FILO),因此可以采用最大优先级队列进行实现,与用最小优先级队列实现队列思想类似,按照元素出现的顺序进行标记元素的优先级,数据越是靠后,优先级越高。
      
      举例说明采用最小优先级队列实现先进先出队列,现在有一组数A={24,15,27,5,43,87,34}共六个数,假设数组下标从1开始,以元素所在数组中的下标为优先级创建优先级队列,队列中元素出入时候调整最小优先级队列。操作过程如下图所示:

    《算法导论课后习题》

    题目如下:请给出一个时间为O(nlgk)、用来将k个已排序链表合并为一个排序链表的算法。此处n为所有输入链表中元素的总数。(提示:用一个最小堆来做k路合并)。

    看到题目第个想到的是归并排序过程中的归并操作子过程,从头开始两两比较,找出最小的,然后接着往后比较,常用的是2路归并。而题目给的是k个已排好序的链表(k>=2)。如果没有提示,我半天不知道如何去实现,幸好提示说用最小堆来做k路合并,于是我想到可以这样做:创建一个大小为k的数组,将k个链表中的第一个元素依次存放到数组中,然后将数组调整为最小堆,这样保证数组的第一个元素是最小的,假设为min,将min从最小堆取出并存放到最终结果的链表中,此时将min所在链表的下一个元素到插入的最小堆中,继续上面的操作,直到堆中没有元素为止。举个例子如下图所示(只给出不部分操作):

    最终结果如下图所示:

    总结:

    对于一个有优先级的无序事件,按照优先级的顺序进行队列的进出,实现的时间复杂度是O(lgn)
    ————————————————————————————————————————————

    线性时间的排序

    算法线性时间的排序算法主要是有3种,计数排序,基数排序,桶排序。他们不需要比较操作,是通过元素本身的位置来进行排序的,因而需要额外的存储空闲,但是可以有线性的时间复杂度O(n)。同时这三种排序算法都是稳定的。

    计数排序

    就是用一个额外的数组记录每个元素出现的次数,同时利用斐波那契思想将顺序的时间相加起来,那么就得出了每个元素前面有多少个比它小的元素,最后按照这个额外的数组,直接将数据放置在对应的位置即可。

    计数排序假设n个输入元素中的每一个都介于0和k之间的整数,k为n个数中最大的元素。当k=O(n)时,计数排序的运行时间为θ(n)。计数排序的基本思想是:对n个输入元素中每一个元素x,统计出小于等于x的元素个数,根据x的个数可以确定x在输出数组中的最终位置。此过程需要引入两个辅助存放空间,存放结果的B[1…n],用于确定每个元素个数的数组C[0…k]。

    算法的具体步骤如下:

    (1)根据输入数组A中元素的值确定k的值,并初始化C[1…k]= 0;
    (2)遍历输入数组A中的元素,确定每个元素的出现的次数,并将A中第i个元素出现的次数存放在C[A[i]]中,然后C[i]=C[i]+C[i-1],在C中确定A中每个元素前面有多个元素;
    (3)逆序遍历数组A中的元素,在C中查找A中出现的次数,并结果数组B中确定其位置,然后将其在C中对应的次数减少1。

    举个例子说明其过程,假设输入数组A=<2,5,3,0,2,3,0,3>,计数排序过程如下:

    基数排序

    就是按照基数的大小,从低位到高位来进行排序,首先按照元素的低位进行排序,在排序后的序列上,按照元素的高位在排序,一次从低到高排序,完成最后的排序。低位的排序是按照计数排序来执行的。

    基数排序排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序,它的时间复杂度可达到线性阶:O(n)。对于十进制数来说,每一位的在[0,9]之中,d位的数,则有d列。基数排序首先按低位有效数字进行排序,然后逐次向上一位进行排序,直到最高位排序结束。

    举例说明基数排序过程,如下图所示:

    基数排序算法很直观,假设长度为n的数组A中,每个元素都有d位数字,其中第1位是最低位,第d位是最高位。

    桶排序

    比较简单,就是将待序列分为不同的区间,每个区间当成一个桶,在自己桶里面先排序好,然后把各个桶的数据连在一起就可以了。但是这个需要有额外的通的开销。
    计数排序假设输入是由一个小范围内的整数构成,而桶排序则假设输入由一个随机过程产生的,该过程将元素均匀而独立地分布在区间[0,1)上。当桶排序的输入符合均匀分布时,即可以线性期望时间运行。桶排序的思想是:把区间[0,1)划分成n个相同大小的子区间,成为桶(bucket),然后将n个输入数分布到各个桶中去,对各个桶中的数进行排序,然后按照次序把各个桶中的元素列出来即可。

    总结

    线性时间的排序方法相对于比较排序在时间复杂度上有提高,但是同时需要牺牲额外的空间开销,这也是正常的。
    ————————————————————————————————————————————

    中位数和顺序统计学

    本章所讨论的问题是在一个由n个不同数值构成的集合中选择第i个顺序统计量问题。主要讲的内容是如何在线性时间内O(n)时间内在集合S中选择第i小的元素,最基本的是选择集合的最大值和最小值。一般情况下选择的元素是随机的,最大值和最小值是特殊情况,书中重点介绍了如何采用分治算法来实现选择第i小的元素,并借助中位数进行优化处理,保证最坏保证运行时间是线性的O(n)。

    1、基本概念

    顺序统计量:在一个由n个元素组成的集合中,第i个顺序统计量是值该集合中第i小的元素。例如最小值是第1个顺序统计量,最大值是第n个顺序统计量。
      
    中位数:一般来说,中位数是指它所在集合的“中间元素”,当n为奇数时,中位数是唯一的,出现位置为n/2;当n为偶数时候,存在两个中位数,位置分别为n/2(上中位数)和n/2+1(下中位数)。

    2、选择问题描述

    输入:一个包含n个(不同的)数的集合A和一个数i,1≤i≤n。
    输出:元素x∈A,它恰大于A中其他的i-1个元素。

    最直接的办法就是采用一种排序算法先对集合A进行排序,然后输出第i个元素即可。可以采用前面讲到的归并排序、堆排序和快速排序,运行时间为O(nlgn)。接下来书中由浅入深的讲如何在线性时间内解决这个问题。

    一般的选择问题似乎要比选择最大值和最小值要难,但是这两种问题的运行时间是相同的,都是θ(n)。书中介绍了采用分治算法解决一般的选择问题,其过程与快速排序过程中划分类似。每次划分集合可以确定一个元素的最终位置,根据这个位置可以判断是否是我们要求的第i小的元素。如果不是,那么我们只关心划分产出两个子部分中的其中一个,根据i的值来判断是前一个还是后一个,然后接着对子数组进行划分,重复此过程,直到找到第i个小的元素。划分可以采用随机划分,这样能够保证期望时间是θ(n)(假设所有元素是不同的)。

    给个例子说明此过程,假设现有集合A={32,23,12,67,45,78,10,39,9,58},要求其第5小的元素,假设在划分过程中以总是以最后一个元素为主元素进行划分。执行过程如下图所示:

    本章中的选择算法之所以具有线性运行时间,是因为这些算法没有进行排序,线性时间的行为并不是因为对输入做假设所得到的结果。

    ————————————————————————————————————————————

    散列表

    本章介绍了散列表(hash table)的概念、散列函数的设计及散列冲突的处理。散列表类似与字典的目录,查找的元素都有一个key与之对应,在实践当中,散列技术的效率是很高的,合理的设计散函数和冲突处理方法,可以使得在散列表中查找一个元素的期望时间为O(1)。散列表是普通数组概念的推广,在散列表中,不是直接把关键字用作数组下标,而是根据关键字通过散列函数计算出来的。在STL中map容器的功能就是散列表的功能,但是map采用的是红黑树实现的,后面接着学习

    1、直接寻址表

    当关键字的的全域(范围)U比较小的时,直接寻址是简单有效的技术,一般可以采用数组实现直接寻址表,数组下标对应的就是关键字的值,即具有关键字k的元素被放在直接寻址表的槽k中。直接寻址表的字典操作实现比较简单,直接操作数组即可以,只需O(1)的时间。

    2、散列表

    直接寻址表的不足之处在于当关键字的范围U很大时,在计算机内存容量的限制下,构造一个存储|U|大小的表不太实际。当存储在字典中的关键字集合K比所有可能的关键字域U要小的多时,散列表需要的存储空间要比直接寻址表少的很多。散列表通过散列函数h计算出关键字k在槽的位置。散列函数h将关键字域U映射到散列表T[0…m-1]的槽位上。即h:U->{0,1…,m-1}。采用散列函数的目的在于缩小需要处理的小标范围,从而降低了空间的开销。
      
      散列表存在的问题:两个关键字可能映射到同一个槽上,即碰撞(collision)。需要找到有效的办法来解决碰撞。

    3、散列函数

    好的散列函数的特点是每个关键字都等可能的散列到m个槽位上的任何一个中去,并与其他的关键字已被散列到哪一个槽位无关。多数散列函数都是假定关键字域为自然数N={0,1,2,…},如果给的关键字不是自然数,则必须有一种方法将它们解释为自然数。例如对关键字为字符串时,可以通过将字符串中每个字符的ASCII码相加,转换为自然数。

    书中介绍了三种设计方案:除法散列法、乘法散法和全域散列法。

    (1)除法散列法

    通过取k除以m的余数,将关键字k映射到m个槽的某一个中去。散列函数为:h(k)=k mod m 。m不应是2的幂,通常m的值是与2的整数幂不太接近的质数。

    (2)乘法散列法

    这个方法看的时候不是很明白,没有搞清楚什么意思,先将基本的思想记录下来,日后好好消化一下。乘法散列法构造散列函数需要两个步骤。第一步,用关键字k乘上常数A(0<A<1),并抽取kA的小数部分。然后,用m乘以这个值,再取结果的底。散列函数如下:h(k) = m(kA mod 1)。

    (3)全域散列

    给定一组散列函数H,每次进行散列时候从H中随机的选择一个散列函数h,使得h独立于要存储的关键字。全域散列函数类的平均性能是比较好的。

    4、碰撞处理

    通常有两类方法处理碰撞:开放寻址(Open Addressing)法和链接(Chaining)法。前者是将所有结点均存放在散列表T[0…m-1]中;后者通常是把散列到同一槽中的所有元素放在一个链表中,而将此链表的头指针放在散列表T[0…m-1]中。

    (1)开放寻址法

    所有的元素都在散列表中,每一个表项或包含动态集合的一个元素,或包含NIL。这种方法中散列表可能被填满,以致于不能插入任何新的元素。在开放寻址法中,当要插入一个元素时,可以连续地检查或探测散列表的各项,直到有一个空槽来放置待插入的关键字为止。有三种技术用于开放寻址法:线性探测、二次探测以及双重探测。

    <1>线性探测

    给定一个普通的散列函数h’:U —>{0,1,…,m-1},线性探测方法采用的散列函数为:h(k,i) = (h’(k)+i)mod m,i=0,1,…,m-1
      
    探测时从i=0开始,首先探查T[h’(k)],然后依次探测T[h’(k)+1],…,直到T[h’(k)+m-1],此后又循环到T[0],T[1],…,直到探测到T[h’(k)-1]为止。探测过程终止于三种情况:
      (1)若当前探测的单元为空,则表示查找失败(若是插入则将key写入其中);
      (2)若当前探测的单元中含有key,则查找成功,但对于插入意味着失败;
      (3)若探测到T[h’(k)-1]时仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满)。
     
    线性探测方法较容易实现,但是存在一次群集问题,即连续被占用的槽的序列变的越来越长。采用例子进行说明线性探测过程,已知一组关键字为(26,36,41,38,44,15,68,12,6,51),用除余法构造散列函数,初始情况如下图所示:

    散列过程如下图所示:

    <2>二次探测

    二次探测法的探查序列是:h(k,i) =(h’(k)+i*i)%m ,0≤i≤m-1 。初次的探测位置为T[h’(k)],后序的探测位置在次基础上加一个偏移量,该偏移量以二次的方式依赖于i。该方法的缺陷是不易探查到整个散列空间。

    <3>双重散列

    该方法是开放寻址的最好方法之一,因为其产生的排列具有随机选择的排列的许多特性。采用的散列函数为:h(k,i)=(h1(k)+ih2(k)) mod m。其中h1和h2为辅助散列函数。初始探测位置为T[h1(k)],后续的探测位置在此基础上加上偏移量h2(k)模m。

    (2)链接法

    将所有关键字为同义词的结点链接在同一个链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组T[0…m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于1,但一般均取α≤1。

    举例说明链接法的执行过程,设有一组关键字为(26,36,41,38,44,15,68,12,6,51),用除余法构造散列函数,初始情况如下图所示:

    最终结果如下图所示:

    5、字符串散列

    通常都是将元素的key转换为数字进行散列,如果key本身就是整数,那么散列函数可以采用keymod tablesize(要保证tablesize是质数)。而在实际工作中经常用字符串作为关键字,例如身姓名、职位等等。这个时候需要设计一个好的散列函数进程处理关键字为字符串的元素。

    有以下几种处理方法:

    方法1:将字符串的所有的字符的ASCII码值进行相加,将所得和作为元素的关键字。设计的散列函数如下所示:

    1 int hash(const string& key,int tablesize)
    2 {
    3     int hashVal = 0;
    4     for(int i=0;i<key.length();i++)
    5            hashVal += key[i];
    6     return hashVal % tableSize;
    7 }
    

    此方法的缺点是不能有效的分布元素,例如假设关键字是有8个字母构成的字符串,散列表的长度为10007。字母最大的ASCII码为127,按照方法1可得到关键字对应的最大数值为127×8=1016,也就是说通过散列函数映射时只能映射到散列表的槽0-1016之间,这样导致大部分槽没有用到,分布不均匀,从而效率低下。
      
    方法2:假设关键字至少有三个字母构成,散列函数只是取前三个字母进行散列。设计的散列函数如下所示:

    1 int hash(const string& key,int tablesize)
    2 {
    3         //27 represents the number of letters plus the blank
    4         return (key[0]+27*key[1]+729*key[2])%tablesize;
    5 }
    

    该方法只是取字符串的前三个字符的ASCII码进行散列,最大的得到的数值是2851,如果散列的长度为10007,那么只有28%的空间被用到,大部分空间没有用到。因此如果散列表太大,就不太适用。

    方法3:借助Horner’s 规则,构造一个质数(通常是37)的多项式,(非常的巧妙,不知道为何是37)。计算公式为:key[keysize-i-1]37^i,0<=i<keysize求和。设计的散列函数如下所示:

     1 int hash(const string & key,int tablesize)
     2 {
     3         int hashVal = 0;
     4         for(int i =0;i<key.length();i++)
     5             hashVal = 37*hashVal + key[i];
     6         hashVal %= tableSize;
     7         if(hashVal<0)  //计算的hashVal溢出
     8            hashVal += tableSize;
     9        return hashVal;
    10 }
    

    该方法存在的问题是如果字符串关键字比较长,散列函数的计算过程就变长,有可能导致计算的hashVal溢出。针对这种情况可以采取字符串的部分字符进行计算,例如计算偶数或者奇数位的字符。

    6、再散列(rehashing)——再散列可以保证平均的查找复杂度是不会变得

    如果散列表满了,再往散列表中插入新的元素时候就会失败。这个时候可以通过创建另外一个散列表,使得新的散列表的长度是当前散列表的2倍多一些,重新计算各个元素的hash值,插入到新的散列表中。再散列的问题是在什么时候进行最好,有三种情况可以判断是否该进行再散列:

    (1)当散列表将快要满了,给定一个范围,例如散列被中已经被用到了80%,这个时候进行再散列。
    (2)当插入一个新元素失败时候,进行再散列。
    (3)根据装载因子(存放n个元素的、具有m个槽位的散列表T,装载因子α=n/m,即每个链子中的平均存储的元素数目)进行判断,当装载因子达到一定的阈值时候,进行在散列。
      
    在采用链接法处理碰撞问题时,采用第三种方法进行在散列效率最好。

    ————————————————————————————————————————————

    红黑树

    红黑树是一种二叉查找树,但在每个结点上增加了一个存储位表示结点的颜色,可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。本章主要介绍了红黑树的性质、左右旋转、插入和删除。重点分析了在红黑树中插入和删除元素的过程,分情况进行详细讨论。一棵高度为h的二叉查找树可以实现任何一种基本的动态集合操作,如SEARCH、PREDECESSOR、SUCCESSOR、MIMMUM、MAXMUM、INSERT、DELETE等。当二叉查找树的高度较低时,这些操作执行的比较快,但是当树的高度较高时,这些操作的性能可能不比用链表好。红黑树(red-black tree)是一种平衡的二叉查找树,它能保证在最坏情况下,基本的动态操作集合运行时间为O(lgn)。本章内容有些复杂,看了两天,才大概清楚其插入和删除过程,日后需要经常回顾,争取完全消化掉。红黑树的用途非常广泛,例如STL中的map就是采用红黑树实现的,效率非常之高,有机会可以研究一下STL的源代码。

    1、红黑树的性质

    红黑树中的每个结点包含五个域:color、key、left、right和parent。如果某结点没有一个子结点或父结点,则该结点相应的指针parent域包含值为NIL(NIL并是是空指针,此处有些迷惑,一会解释)。把NIL视为指向红黑树的外结点(叶子)的指针,而把带关键字的结点视为红黑树的内结点。红黑树结点结构如下所示:

     1 #define RED  0
     2 #define BLACK 1
     3 struct RedBlackTreeNode
     4 { 
     5     T key;
     6     struct RedBlackTreeNode * parent;
     7     struct RedBlackTreeNode * left;
     8     struct RedBlackTreeNode * right;
     9     int color;
    10 };
    

    红黑树的性质如下:

    (1)每个结点或是红色,或是黑色。
    (2)根结点是黑色。
    (3)每个叶子结点(NIL)是黑色。
    (4)如果有一个结点是红色,则它的两个儿子都是黑色。
    (5)对每个结点,从该结点到其孙子结点的所有路径上包含相同数目的黑色结点。

    如下图是一棵红黑树:

    从图可以看出NIL不是空指针,而是一个叶子结点。实际操作的时候可以将NIL视为哨兵,这样便于对黑红色进行操作。红黑树的操作主要是对内部结点操作,因为内部结点存储了关键字的值。书中为了便于讨论,忽略了叶子结点的,如是上图红黑树变成如下图所示:

    书中给出了黑高度的概念:从某个结点x出发(不包含该结点)到达一个叶子结点的任意一条路径上,黑色结点的个数称为该结点的黑高度。由红黑树的性质(5)可知,从该结点出发的所有下降路径都有相同的黑色结点个数。红黑树的黑高度定义为其根结点的黑高度。
      书中给出了一个引理来说明为什么红黑树是一种好的查找树,并对引理进行了证明(采用归纳法进行证明的,需要很强的归纳推理知识,正是我的不足之处,看书的痛苦在于此)。
    引理:一棵有n个内结点的红黑树的高度之多为2lg(n+1)。

    比较与疑问:

    1.红黑树和平衡二叉树(AVL树)的区别与联系
    2.红黑树为啥增加插入的节点要置为红节点
    3.红黑树在哪里用的比较多,它相对其他的平衡搜索树有何优点?

    解答:

    1, 红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。

    红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构 能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高。

    平衡二叉树严格的高度控制,左右子树的高度差距不能大于1,这回导致插入删除有较多的旋转调整的步骤,并且其树的高度一定是lgn,也就是说这种树的平均时间复杂度就是O(lgn)
    但是红黑树,只用保证任何节点到叶子节点均包含相同数目的黑色节点,通过颜色来约束树的形状,主要有以下几个特征:
    1.红黑树的高度总是低于2lg(n+1),n为节点的个数
    2.红黑树的时间复杂度为O(h(x))= O(2lg(n+1))=O(lgn)
    3.任何插入删除导致的不平衡都可以在三次旋转操作内完成平衡,降低了实现的复杂度。

    查找较多的可以选择用avltree、插入删除较多的可以用rbtree

    1、黑色,如果是黑色,那么不管原来的红黑树是什么样的,这样一定会破坏平衡,因为原来的树是平衡的,现在在这一条路径上多了一个黑色,必然违反了性质5(不记得的时候多看几遍性质,并理解是最好的)。

    2、红色,如果新插入的点是红色的,那么也有可能会破坏平衡,主要可能是违反了性质4,比如上图中,新插入的点21的父节点22为红色。但是却有一种特殊情况,比如上图中,如果我插入一个key=0的节点。把0这个节点置为红色,并不会影响原来树的平衡,因为0的父节点是黑色。
    如下图:

    好歹也有不需要调整的情况,所以还是选择把新插入的节点颜色置为红色。

    AVL树

    平衡二叉树,一般是用平衡因子差值决定并通过旋转来实现,左右子树树高差不超过1,那么和红黑树比较它是严格的平衡二叉树,平衡条件非常严格(树高差只有1),只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL树适合用于插入删除次数比较少,但查找多的情况。
    应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。

    红黑树:平衡二叉树,通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束,确保没有一条路径会比其他路径长2倍,因而是近似平衡的。所以相对于严格要求平衡的AVL树来说,它的旋转保持平衡次数较少。用于搜索时,插入删除次数多的情况下我们就用红黑树来取代AVL。

    红黑树应用比较广泛:

    · 广泛用在C++的STL中。map和set都是用红黑树实现的。
    · 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。
    · epoll在内核中的实现,用红黑树管理事件块
    · nginx中,用红黑树管理timer等
    · Java的TreeMap实现

        B树,B+树:它们特点是一样的,是多路查找树,一般用于数据库中做索引,因为它们分支多层数少,因为磁盘IO是非常耗时的,而像大量数据存储在磁盘中所以我们要有效的减少磁盘IO次数避免磁盘频繁的查找。
    

    B+树是B树的变种树,有n棵子树的节点中含有n个关键字,每个关键字不保存数据,只用来索引,数据都保存在叶子节点。是为文件系统而生的。

    B+树相对B树磁盘读写代价更低:因为B+树非叶子结点只存储键值,单个节点占空间小,索引块能够存储更多的节点,从磁盘读索引时所需的索引块更少,所以索引查找时I/O次数较B-Tree索引少,效率更高。而且B+Tree在叶子节点存放的记录以链表的形式链接,范围查找或遍历效率更高。Mysql InnoDB用的就是B+Tree索引。

    Trie树:
    又名单词查找树,一种树形结构,常用来操作字符串。它是不同字符串的相同前缀只保存一份。

    相对直接保存字符串肯定是节省空间的,但是它保存大量字符串时会很耗费内存(是内存)。
    类似的有:前缀树(prefix tree),后缀树(suffix tree),radix tree(patricia tree, compactprefix tree),crit-bit tree(解决耗费内存问题),以及前面说的double array trie。

    前缀树:字符串快速检索,字符串排序,最长公共前缀,自动匹配前缀显示后缀。
    后缀树:查找字符串s1在s2中,字符串s1在s2中出现的次数,字符串s1,s2最长公共部分,最长回文串。

    trie 树的一个典型应用是前缀匹配,比如下面这个很常见的场景,在我们输入时,搜索引擎会给予提示。还有比如IP选路,也是前缀匹配,一定程度会用到trie。

    面试中红黑树常考问题

    1.stl中的set底层用的什么数据结构?
    2.红黑树的数据结构怎么定义的?
    3.红黑树有哪些性质?
    4.红黑树的各种操作的时间复杂度是多少?
    5.红黑树相比于BST和AVL树有什么优点?
    6.红黑树相对于哈希表,在选择使用的时候有什么依据?
    7.如何扩展红黑树来获得比某个结点小的元素有多少个?
    8.扩展数据结构有什么步骤?
    9 为什么一般hashtable的桶数会取一个素数

    详细解答

    1.stl中的set底层用的什么数据结构?

    红黑树

    2.红黑树的数据结构怎么定义?

     1. enum Color  
     2. {  
     3.           RED = 0,  
     4.           BLACK = 1  
     5. };  
     6.   
     7. struct RBTreeNode  
     8. {  
     9.            struct RBTreeNode*left, *right, *parent;  
     10.            int   key;  
     11.            int data;  
     12.            Color color;  
     13. };  
    

    3.红黑树有哪些性质?

    一般的,红黑树,满足以下性质,即只有满足以下全部性质的树,我们才称之为红黑树:

    1)每个结点要么是红的,要么是黑的。
    2)根结点是黑的。
    3)每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。
    4)如果一个结点是红的,那么它的俩个儿子都是黑的。
    5)对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

    4.红黑树的各种操作的时间复杂度是多少?

    能保证在最坏情况下,基本的动态几何操作的时间均为O(lgn)

    5.红黑树相比于BST和AVL树有什么优点?

    红黑树是牺牲了严格的高度平衡的优越条件为代价,它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。

    相比于BST,因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度,所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的,这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。

    红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高,所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多,但是他们的查找效率都是O(logN),所以红黑树应用还是高于AVL树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用 AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的

    6.红黑树相对于哈希表,在选择使用的时候有什么依据?

    权衡三个因素:== 查找速度, 数据量, 内存使用,可扩展性。==

    总体来说,hash查找速度会比map快,而且查找速度基本和数据量大小无关,属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n) 小,hash还有hash函数的耗时,明白了吧,如果你考虑效率,特别是在元素达到一定数量级时,考虑考虑hash。但若你对内存使用特别严格, 希望程序尽可能少消耗内存,那么一定要小心,hash可能会让你陷入尴尬,特别是当你的hash对象特别多时,你就更无法控制了,而且 hash的构造速度较慢。

    红黑树并不适应所有应用树的领域。如果数据基本上是静态的,那么让他们待在他们能够插入,并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的,例如,做一个哈希表,性能可能会更好一些。

    在实际的系统中,例如,需要使用动态规则的防火墙系统,使用红黑树而不是散列表被实践证明具有更好的伸缩性。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。
    红黑树通过扩展节点域可以在不改变时间复杂度的情况下得到结点的秩。

    7.如何扩展红黑树来获得比某个结点小的元素有多少个?

    这其实就是求节点元素的顺序统计量,当然任意的顺序统计量都可以需要在O(lgn)时间内确定。
    在每个节点添加一个size域,表示以结点 x 为根的子树的结点树的大小
    则有size[x] = size[[left[x]] + size [right[x]] + 1;,这时候红黑树就变成了一棵顺序统计树。

    利用size域可以做两件事:

    1). 找到树中第i小的结点;
     1. OS-SELECT(x;,i)  
     2. r = size[left[x]] + 1;  
     3. if i == r  
     4.      return x  
     5. elseif i < r  
     6.      return OS-SELECT(left[x], i)  
     7. else return OS-SELECT(right[x],  i)  
    

    思路:size[left[x]]表示在对x为根的子树进行中序遍历时排在x之前的个数,递归调用的深度不会超过O(lgn);

    2).确定某个结点之前有多少个结点,也就是我们要解决的问题;
     1. OS-RANK(T,x)  
     2. r = x.left.size + 1;  
     3. y = x;  
     4. while y != T.root  
     5.          if y == y.p.right  
     6.                  r = r + y.p.left.size +1  
     7.          y = y.p  
     8. return r  
    

    思路:x的秩可以视为在对树的中序遍历种,排在x之前的结点个数加上一。最坏情况下,OS-RANK运行时间与树高成正比,所以为O (lgn).

    8.扩展数据结构有什么步骤?

    1).选择基础数据结构;
    2).确定要在基础数据结构种添加哪些信息;
    3).验证可用基础数据结构上的基本修改操作来维护这些新添加的信息;
    4).设计新的操作。

    9 为什么一般hashtable的桶数会取一个素数

    设有一个哈希函数
    H( c ) = c % N;
    当N取一个合数时,最简单的例子是取2n,比如说取23=8,这时候
    H( 11100(二进制) ) = H( 28 ) = 4
    H( 10100(二进制) ) = H( 20 )= 4

    这时候c的二进制第4位(从右向左数)就”失效”了,也就是说,无论第c的4位取什么值,都会导致H( c )的值一样.这时候c的第四位就根本不参与H( c )的运算,这样H( c )就无法完整地反映c的特性,增大了导致冲突的几率.

    取其他合数时,都会不同程度的导致c的某些位”失效”,从而在一些常见应用中导致冲突.
    但是取质数,基本可以保证c的每一位都参与H( c )的运算,从而在常见应用中减小冲突几率

    ———————————————————————————————————————————

    动态规划(dynamic programming)

    通过组合子问题的解而解决整个问题的。分治算法是指将问题划分为一些独立的子问题,递归的求解各个问题,然后合并子问题的解而得到原问题的解。例如归并排序,快速排序都是采用分治算法思想。

    而动态规划与此不同,适用于子问题不是独立的情况,也就是说各个子问题包含有公共的子问题。如在这种情况下,用分治算法则会重复做不必要的工作。采用动态规划算法对每个子问题只求解一次,将其结果存放到一张表中,以供后面的子问题参考,从而避免每次遇到各个子问题时重新计算答案。

    动态规划与分治法之间的区别:

    (1)分治法是指将问题分成一些独立的子问题,递归的求解各子问题
    (2)动态规划适用于这些子问题不是独立的情况,也就是各子问题包含公共子问题

    动态规划通常用于最优化问题(此类问题一般有很多可行解,我们希望从这些解中找出一个具有最优(最大或最小)值的解)。动态规划算法的设计分为以下四个步骤:

    (1)描述最优解的结构
    (2)递归定义最优解的值
    (3)按自低向上的方式计算最优解的值
    (4)由计算出的结果构造一个最优解

    1、基本概念

    动态规划是通过组合子问题的解而解决整个问题的,通过将问题分解为相互不独立(各个子问题包含有公共的子问题,也叫重叠子问题)的子问题,对每个子问题求解一次,将其结果保存到一张辅助表中,避免每次遇到各个子问题时重新计算。动态规划通常用于解决最优化问题,

    其设计步骤如下:

    (1)描述最优解的结构。
    (2)递归定义最优解的值。
    (3)按自底向上的方式计算最优解的值。
    (4)由计算出的结果构造出一个最优解。

    第一步是选择问题的在什么时候会出现最优解,通过分析子问题的最优解而达到整个问题的最优解。在第二步,根据第一步得到的最优解描述,将整个问题分成小问题,直到问题不可再分为止,层层选择最优,构成整个问题的最优解,给出最优解的递归公式。第三步根据第二步给的递归公式,采用自底向上的策略,计算每个问题的最优解,并将结果保存到辅助表中。第四步骤是根据第三步中的最优解,借助保存在表中的值,给出最优解的构造过程。

    动态规划与分治法之间的区别:

    (1) 分治法是指将问题分成一些独立的子问题,递归的求解各子问题。
    (2) 动态规划适用于这些子问题不是独立的情况,也就是各子问题包含公共子问题。

    2、动态规划基础

    什么时候可以使用动态规范方法解决问题呢?这个问题需要讨论一下,书中给出了采用动态规范方法的最优化问题中的两个要素:最优子结构和重叠子结构。

    1)最优子结构

    最优子结构是指问题的一个最优解中包含了其子问题的最优解。在动态规划中,每次采用子问题的最优解来构造问题的一个最优解。寻找最优子结构,遵循的共同的模式:

    (1)问题的一个解可以是做一个选择,得到一个或者多个有待解决的子问题。
    (2)假设对一个给定的问题,已知的是一个可以导致最优解的选择,不必关心如何确定这个选择。
    (3)在已知这个选择后,要确定哪些子问题会随之发生,如何最好地描述所得到的子问题空间。
    (4)利用“剪贴”技术,来证明问题的一个最优解中,使用的子问题的解本身也是最优的。

    最优子结构在问题域中以两种方式变化:

    (1)有多少个子问题被使用在原问题的一个最优解中。
    (2)在决定一个最优解中使用哪些子问题时有多少个选择。

    动态规划按照自底向上的策略利用最优子结构,即:首先找到子问题的最优解,解决子问题,然后逐步向上找到问题的一个最优解。为了描述子问题空间,可以遵循这样一条有效的经验规则,就是尽量保持这个空间简单,然后在需要时再扩充它。

    注意:在不能应用最优子结构的时候,就一定不能假设它能够应用。 警惕使用动态规划去解决缺乏最优子结构的问题!

    使用动态规划时,子问题之间必须是相互独立的!可以这样理解,N个子问题域互不相干,属于完全不同的空间。

    2)重叠子问题

    用来解决原问题的递归算法可以反复地解同样的子问题,而不是总是产生新的子问题。重叠子问题是指当一个递归算法不断地调用同一个问题。动态规划算法总是充分利用重叠子问题,通过每个子问题只解一次,把解保存在一个需要时就可以查看的表中,每次查表的时间为常数。

    由计算出的结果反向构造一个最优解:把动态规划或者是递归过程中作出的每一次选择(记住:保存的是每次作出的选择)都保存下来,在最后就一定可以通过这些保存的选择来反向构造出最优解。

    做备忘录的递归方法:这种方法是动态规划的一个变形,它本质上与动态规划是一样的,但是比动态规划更好理解!

    (1) 使用普通的递归结构,自上而下的解决问题。
    (2) 当在递归算法的执行中每一次遇到一个子问题时,就计算它的解并填入一个表中。以后每次遇到该子问题时,只要查看并返回表中先前填入的值即可。

    3、总结

    动态规划的核心就是找到问题的最优子结构,在找到最优子结构之后的消除重复子问题。最终无论是采用动态规划的自底向上的递推,还是备忘录,或者是备忘录的变型,都可以轻松的找出最优解的构造过程。

    4、思考

    使用动态规划首先确定解决的问题是否具有最优子结构,那么随之而来的是,什么是最优子结构?

    最优子结构就是说,原文题的最优解也是子问题的最优解,例如算导上面的钢条切割的问题,因为原问题是n长度钢条切割的最优解,那么子问题是n-i长度的钢条的最优解,这样的问题是最优子结构的问题,我们可以认为存在一个最优的切割方法导致了出现了n-i长度的钢条,那么就是i长度和n-i长度钢条的最优切割方法决定了n长度钢条的最优切割方法,也就是说子问题的最优解就是原问题的最优解。

    那么什么样的问题,不满足最优子结构呢?

    有一个网友给出的例子;
    给定一个n*m的矩阵,每个格子里有一个正整数,从左上角开始到右下角,每次只能向下或向右走,问经过的数之和模k后最大能是多少?

    定义状态f(i,j)表示从左上角走到i,j的最优解(这里最优解指经过的数之和模k最大),显然从f(i,j)转移到f(i+1,j)或f(i,j+1)显然是不对的。 也就是说,这里一个问题的最优解不一定包含其子问题的最优解,所以不满足最优子结构。。

    这个例子的重点就是在从f(i,j)转移到f(i+1,j)或f(i,j+1),即f(i,j)的最优解并不代表是f(i+1,j)的最优解,因为f(i+1,j)的最优解包含路径很有可能并不会经过f(i,j),即不满足最优子结构!!!!

    那么这个问题该如何解决呢????暴力破解,从头开始枚举向下向右的每一个路径,计算路径的最小值。

    ———————————————————————————————————————————

    贪心算法

    贪心算法是通过一系列的选择来给出某一个问题的最优解,每次选择一个当前(看起来是)最佳的选择。

    贪心算法解决问题的步骤为:

    (1)决定问题的最优子结构
    (2)设计出一个递归解
    (3)证明在递归的任一阶段,最优选择之一总是贪心选择。保证贪心选择总是安全的。
    (4)证明通过贪心选择,所有子问题(除一个意外)都为空。
    (5)设计出一个实现贪心策略的递归算法。
    (6)将递归算法转换成迭代算法。

    什么时候才能使用贪心算法的呢?书中给出了贪心算法的两个性质,只有最优化问题满足这些性质,就可采用贪心算法解决问题。

    (1)贪心选择性质:一个全局最优解可以通过举办最优解(贪心)选择来达到。即:当考虑做选择时,只考虑对当前问题最佳的选择而不考虑子问题的结果。而在动态规划中,每一步都要做出选择,这些选择依赖于子问题的解。动态规划一般是自底向上,从小问题到大问题。贪心算法通常是自上而下,一个一个地做贪心选择,不断地将给定的问题实例规约为更小的子问题。
    (2)最优子结构:问题的一个最优解包含了其子问题的最优解。

    动态规划与贪心的区别:

    贪心算法:

    (1)贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一部之前的最优解则不作保留;
    (2)由(1)中的介绍,可以知道贪心法正确的条件是:每一步的最优解一定包含上一步的最优解。

    动态规划算法:

    (1)全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解 ;
    (2)动态规划的关键是状态转移方程,即如何由以求出的局部最优解来推导全局最优解 ;
    (3)边界条件:即最简单的,可以直接得出的局部最优解。

    0-1背包问题描述

    有一个窃贼在偷窃一家商店时发现有n件物品,第i件物品价值为vi元,重量为wi,假设vi和wi都为整数。他希望带走的东西越值钱越好,但他的背包中之多只能装下W磅的东西,W为一整数。他应该带走哪几样东西?

    0-1背包问题中:每件物品或被带走,或被留下,(需要做出0-1选择)。小偷不能只带走某个物品的一部分或带走两次以上同一个物品。

    部分背包问题:小偷可以只带走某个物品的一部分,不必做出0-1选择。

    0-1背包问题解决方法

    0-1背包问题是个典型举办子结构的问题,但是只能采用动态规划来解决,而不能采用贪心算法。因为在0-1背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较。这种方式形成的问题导致了许多重叠子问题,满足动态规划的特征。动态规划解决0-1背包问题步骤如下:

    0-1背包问题子结构:选择一个给定物品i,则需要比较选择i的形成的子问题的最优解与不选择i的子问题的最优解。分成两个子问题,进行选择比较,选择最优的。

    0-1背包问题递归过程:设有n个物品,背包的重量为w,C[i][w]为最优解。即:

    ———————————————————————————————————————————

    图的搜索

    一、深度优先搜索和广度优先搜索的深入讨论

    深度优先搜索的特点是:

    (1)无论问题的内容和性质以及求解要求如何不同,它们的程序结构都是相同的,即都是深度优先算法(一)和深度优先算法(二)中描述的算法结构,不相同的仅仅是存储结点数据结构和产生规则以及输出要求。

    (2)深度优先搜索法有递归以及非递归两种设计方法。一般的,当搜索深度较小、问题递归方式比较明显时,用递归方法设计好,它可以使得程序结构更简捷易懂。当搜索深度较大时,当数据量较大时,由于系统堆栈容量的限制,递归容易产生溢出,用非递归方法设计比较好。

    (3)深度优先搜索方法有广义和狭义两种理解。广义的理解是,只要最新产生的结点(即深度最大的结点)先进行扩展的方法,就称为深度优先搜索方法。在这种理解情况下,深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是,仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点的算法属于一般的回溯算法范畴。保留全部结点的算法,实际上是在数据库中产生一个结点之间的搜索树,因此也属于图搜索算法的范畴。

    (4)不保留全部结点的深度优先搜索法,由于把扩展望的结点从数据库中弹出删除,这样,一般在数据库中存储的结点数就是深度值,因此它占用的空间较少,所以,当搜索树的结点较多,用其他方法易产生内存溢出时,深度优先搜索不失为一种有效的算法。

    (5)从输出结果可看出,深度优先搜索找到的第一个解并不一定是最优解。
    如果要求出最优解的话,一种方法将是后面要介绍的动态规划法,另一种方法是修改原算法:把原输出过程的地方改为记录过程,即记录达到当前目标的路径和相应的路程值,并与前面已记录的值进行比较,保留其中最优的,等全部搜索完成后,才把保留的最优解输出。

    广度优先搜索法的显著特点是:

    (1)在产生新的子结点时,深度越小的结点越先得到扩展,即先产生它的子结点。为使算法便于实现,存放结点的数据库一般用队列的结构。

    (2)无论问题性质如何不同,利用广度优先搜索法解题的基本算法是相同的,但数据库中每一结点内容,产生式规则,根据不同的问题,有不同的内容和结构,就是同一问题也可以有不同的表示方法。

    (3)当结点到跟结点的费用(有的书称为耗散值)和结点的深度成正比时,特别是当每一结点到根结点的费用等于深度时,用广度优先法得到的解是最优解,但如果不成正比,则得到的解不一定是最优解。这一类问题要求出最优解,一种方法是使用后面要介绍的其他方法求解,另外一种方法是改进前面深度(或广度)优先搜索算法:找到一个目标后,不是立即退出,而是记录下目标结点的路径和费用,如果有多个目标结点,就加以比较,留下较优的结点。把所有可能的路径都搜索完后,才输出记录的最优路径。

    (4)广度优先搜索算法,一般需要存储产生的所有结点,占的存储空间要比深度优先大得多,因此程序设计中,必须考虑溢出和节省内存空间得问题。

    (5)比较深度优先和广度优先两种搜索法,广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索算法法要快些。

    总之,一般情况下,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快,在距离和深度成正比的情况下能较快地求出最优解。因此在选择用哪种算法时,要综合考虑。决定取舍。

    深度优先搜索的图文介绍

    1. 深度优先搜索介绍

    图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。

    它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

    显然,深度优先搜索是一个递归的过程。

    2. 深度优先搜索图解

    2.1 无向图的深度优先搜索

    下面以"无向图"为例,来对深度优先搜索进行演示。

    对上面的图G1进行深度优先遍历,从顶点A开始。

    第1步:访问A。
    第2步:访问(A的邻接点)C。 在第1步访问A之后,接下来应该访问的是A的邻接点,即"C,D,F"中的一个。但在本文的实现中,顶点ABCDEFG是按照顺序存储,C在"D和F"的前面,因此,先访问C。
    第3步:访问(C的邻接点)B。 在第2步访问C之后,接下来应该访问C的邻接点,即"B和D"中一个(A已经被访问过,就不算在内)。而由于B在D之前,先访问B。
    第4步:访问(C的邻接点)D。 在第3步访问了C的邻接点B之后,B没有未被访问的邻接点;因此,返回到访问C的另一个邻接点D。
    第5步:访问(A的邻接点)F。 前面已经访问了A,并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)";因此,此时返回到访问A的另一个邻接点F。
    第6步:访问(F的邻接点)G。
    第7步:访问(G的邻接点)E。
    因此访问顺序是:A -> C -> B -> D -> F -> G -> E

    2.2 有向图的深度优先搜索

    下面以"有向图"为例,来对深度优先搜索进行演示。

    对上面的图G2进行深度优先遍历,从顶点A开始。

    第1步:访问A。
    第2步:访问B。 在访问了A之后,接下来应该访问的是A的出边的另一个顶点,即顶点B。
    第3步:访问C。 在访问了B之后,接下来应该访问的是B的出边的另一个顶点,即顶点C,E,F。在本文实现的图中,顶点ABCDEFG按照顺序存储,因此先访问C。
    第4步:访问E。 接下来访问C的出边的另一个顶点,即顶点E。
    第5步:访问D。 接下来访问E的出边的另一个顶点,即顶点B,D。顶点B已经被访问过,因此访问顶点D。
    第6步:访问F。 接下应该回溯"访问A的出边的另一个顶点F"。
    第7步:访问G。
    因此访问顺序是:A -> B -> C -> E -> D -> F -> G

    广度优先搜索的图文介绍

    1. 广度优先搜索介绍

    广度优先搜索算法(Breadth First Search),又称为"宽度优先搜索"或"横向优先搜索",简称BFS。
    它的思想是:从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。

    换句话说,广度优先搜索遍历图的过程是以v为起点,由近至远,依次访问和v有路径相通且路径长度为1,2…的顶点。

    2. 广度优先搜索图解

    2.1 无向图的广度优先搜索

    下面以"无向图"为例,来对广度优先搜索进行演示。还是以上面的图G1为例进行说明。

    第1步:访问A。
    第2步:依次访问C,D,F。 在访问了A之后,接下来访问A的邻接点。前面已经说过,在本文实现中,顶点ABCDEFG按照顺序存储的,C在"D和F"的前面,因此,先访问C。再访问完C之后,再依次访问D,F。
    第3步:依次访问B,G。 在第2步访问完C,D,F之后,再依次访问它们的邻接点。首先访问C的邻接点B,再访问F的邻接点G。
    第4步:访问E。 在第3步访问完B,G之后,再依次访问它们的邻接点。只有G有邻接点E,因此访问G的邻接点E。
    因此访问顺序是:A -> C -> D -> F -> B -> G -> E

    2.2 有向图的广度优先搜索

    下面以"有向图"为例,来对广度优先搜索进行演示。还是以上面的图G2为例进行说明。

    第1步:访问A。
    第2步:访问B。
    第3步:依次访问C,E,F。 在访问了B之后,接下来访问B的出边的另一个顶点,即C,E,F。前面已经说过,在本文实现中,顶点ABCDEFG按照顺序存储的,因此会先访问C,再依次访问E,F。
    第4步:依次访问D,G。 在访问完C,E,F之后,再依次访问它们的出边的另一个顶点。还是按照C,E,F的顺序访问,C的已经全部访问过了,那么就只剩下E,F;先访问E的邻接点D,再访问F的邻接点G。
    因此访问顺序是:A -> B -> C -> E -> F -> D -> G

    ———————————————————————————————————————————

    图算法之最小生成树

    图算法里面有一个问题就是关于所有路径中的最小加权路径,它对应的实际例子类似电路板里面如何走线效率最高,用的线的长度最小?

    这一类的问题归根到底就是最小生成树的问题,最小生成树即是图中最佳的路径选择,最小生成树的问题是一个典型的贪心算法,每一步都选择权重最小的边。

    求图中的最小生成树的问题主要有两个经典的算法,Kruskal算法和Prim算法下面就这两个算法进行详细的论述:

    Kruskal算法

    最小生成树

    在含有n个顶点的连通图中选择n-1条边,构成一棵极小连通子图,并使该连通子图中n-1条边上权值之和达到最小,则称其为连通网的最小生成树。

    例如,对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。

    克鲁斯卡尔算法介绍

    克鲁斯卡尔(Kruskal)算法,是用来求加权连通图的最小生成树的算法。

    基本思想:按照权值从小到大的顺序选择n-1条边,并保证这n-1条边不构成回路。

    具体做法:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直至森林变成一棵树为止。

    克鲁斯卡尔算法图解
    以上图G4为例,来对克鲁斯卡尔进行演示(假设,用数组R保存最小生成树结果)。

    第1步:将边<E,F>加入R中。
    边<E,F>的权值最小,因此将它加入到最小生成树结果R中。
    第2步:将边<C,D>加入R中。
    上一步操作之后,边<C,D>的权值最小,因此将它加入到最小生成树结果R中。
    第3步:将边<D,E>加入R中。
    上一步操作之后,边<D,E>的权值最小,因此将它加入到最小生成树结果R中。
    第4步:将边<B,F>加入R中。
    上一步操作之后,边<C,E>的权值最小,但<C,E>会和已有的边构成回路;因此,跳过边<C,E>。同理,跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。
    第5步:将边<E,G>加入R中。
    上一步操作之后,边<E,G>的权值最小,因此将它加入到最小生成树结果R中。
    第6步:将边<A,B>加入R中。
    上一步操作之后,边<F,G>的权值最小,但<F,G>会和已有的边构成回路;因此,跳过边<F,G>。同理,跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。
    此时,最小生成树构造完成!它包括的边依次是:<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。

    克鲁斯卡尔算法分析

    根据前面介绍的克鲁斯卡尔算法的基本思想和做法,我们能够了解到,克鲁斯卡尔算法重点需要解决的以下两个问题:

    问题一 对图的所有边按照权值大小进行排序。
    问题二 将边添加到最小生成树中时,怎么样判断是否形成了回路。

    问题一很好解决,采用排序算法进行排序即可。
    问题二,处理方式是:记录顶点在"最小生成树"中的终点,顶点的终点是"在最小生成树中与它连通的最大顶点"(关于这一点,后面会通过图片给出说明)。然后每次需要将一条边添加到最小生存树时,判断该边的两个顶点的终点是否重合,重合的话则会构成回路。 以下图来进行说明:

    在将<E,F> <C,D> <D,E>加入到最小生成树R中之后,这几条边的顶点就都有了终点:
    (01) C的终点是F。
    (02) D的终点是F。
    (03) E的终点是F。
    (04) F的终点是F。
    关于终点,就是将所有顶点按照从小到大的顺序排列好之后;某个顶点的终点就是"与它连通的最大顶点"。 因此,接下来,虽然<C,E>是权值最小的边。但是C和E的重点都是F,即它们的终点相同,因此,将<C,E>加入最小生成树的话,会形成回路。这就是判断回路的方式。
    ————————————————————————————————————————————

    Prim算法

    普里姆算法介绍

    普里姆(Prim)算法,和克鲁斯卡尔算法一样,是用来求加权连通图的最小生成树的算法。

    基本思想
    对于图G而言,V是所有顶点的集合;现在,设置两个新的集合U和T,其中U用于存放G的最小生成树中的顶点,T存放G的最小生成树中的边。 从所有uЄU,vЄ(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v),将顶点v加入集合U中,将边(u, v)加入集合T中,如此不断重复,直到U=V为止,最小生成树构造完毕,这时集合T中包含了最小生成树中的所有边。

    普里姆算法图解

    以上图G4为例,来对普里姆进行演示(从第一个顶点A开始通过普里姆算法生成最小生成树)。

    初始状态:V是所有顶点的集合,即V={A,B,C,D,E,F,G};U和T都是空!
    第1步:将顶点A加入到U中。
    此时,U={A}。
    第2步:将顶点B加入到U中。
    上一步操作之后,U={A}, V-U={B,C,D,E,F,G};因此,边(A,B)的权值最小。将顶点B添加到U中;此时,U={A,B}。
    第3步:将顶点F加入到U中。
    上一步操作之后,U={A,B}, V-U={C,D,E,F,G};因此,边(B,F)的权值最小。将顶点F添加到U中;此时,U={A,B,F}。
    第4步:将顶点E加入到U中。
    上一步操作之后,U={A,B,F}, V-U={C,D,E,G};因此,边(F,E)的权值最小。将顶点E添加到U中;此时,U={A,B,F,E}。
    第5步:将顶点D加入到U中。
    上一步操作之后,U={A,B,F,E}, V-U={C,D,G};因此,边(E,D)的权值最小。将顶点D添加到U中;此时,U={A,B,F,E,D}。
    第6步:将顶点C加入到U中。
    上一步操作之后,U={A,B,F,E,D}, V-U={C,G};因此,边(D,C)的权值最小。将顶点C添加到U中;此时,U={A,B,F,E,D,C}。
    第7步:将顶点G加入到U中。
    上一步操作之后,U={A,B,F,E,D,C}, V-U={G};因此,边(F,G)的权值最小。将顶点G添加到U中;此时,U=V。
    此时,最小生成树构造完成!它包括的顶点依次是:A B F E D C G。

    ————————————————————————————————————————————

    图算法之单源最短路径

    Dijkstra 算法

    (中文名:迪杰斯特拉算法)是由荷兰计算机科学家 Edsger Wybe Dijkstra 提出。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说,如果图中的顶点表示城市,而边上的权重表示城市间开车行经的距离,该算法可以用来找到两个城市之间的最短路径。

    迪杰斯特拉算法介绍

    迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。
    它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。

    基本思想

    通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算)。此外,引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

    初始时,S中只有起点s;U中是除s之外的顶点,并且U中顶点的路径是"起点s到该顶点的路径"。然后,从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 然后,再从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 … 重复该操作,直到遍历完所有顶点。

    操作步骤

    (1) 初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为"起点s到该顶点的距离"[例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。
    (2) 从U中选出"距离最短的顶点k",并将顶点k加入到S中;同时,从U中移除顶点k。
    (3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。
    (4) 重复步骤(2)和(3),直到遍历完所有顶点。
    单纯的看上面的理论可能比较难以理解,下面通过实例来对该算法进行说明。

    迪杰斯特拉算法图解

    以上图G4为例,来对迪杰斯特拉进行算法演示(以第4个顶点D为起点)。

    初始状态:S是已计算出最短路径的顶点集合,U是未计算除最短路径的顶点的集合!
    第1步:将顶点D加入到S中。
    此时,S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。 注:C(3)表示C到起点D的距离是3。
    第2步:将顶点C加入到S中。
    上一步操作之后,U中顶点C到起点D的距离最短;因此,将C加入到S中,同时更新U中顶点的距离。以顶点F为例,之前F到D的距离为∞;但是将C加入到S之后,F到D的距离为9=(F,C)+(C,D)。
    此时,S={D(0),C(3)}, U={A(∞),B(23),E(4),F(9),G(∞)}。
    第3步:将顶点E加入到S中。
    上一步操作之后,U中顶点E到起点D的距离最短;因此,将E加入到S中,同时更新U中顶点的距离。还是以顶点F为例,之前F到D的距离为9;但是将E加入到S之后,F到D的距离为6=(F,E)+(E,D)。
    此时,S={D(0),C(3),E(4)}, U={A(∞),B(23),F(6),G(12)}。
    第4步:将顶点F加入到S中。
    此时,S={D(0),C(3),E(4),F(6)}, U={A(22),B(13),G(12)}。
    第5步:将顶点G加入到S中。
    此时,S={D(0),C(3),E(4),F(6),G(12)}, U={A(22),B(13)}。
    第6步:将顶点B加入到S中。
    此时,S={D(0),C(3),E(4),F(6),G(12),B(13)}, U={A(22)}。
    第7步:将顶点A加入到S中。
    此时,S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}。
    此时,起点D到各个顶点的最短距离就计算出来了:A(22) B(13) C(3) D(0) E(4) F(6) G(12)。
    ————————————————————————————————————————————

    字符串匹配KMP算法

    KMP算法是一种改进的字符串匹配算法。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

    下面先直接给出KMP的算法流程(如果感到一点点不适,没关系,坚持下,稍后会有具体步骤及解释):

    假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。此举意味着失败时,模式串P相对于文本串S向右移动了j - next [j] 位。 换言之,当匹配失败时,模式串向右移动的位数为:失败字符所在位置 - 失败字符对应的next 值(next 数组的求解会在下文的3.3.3节中详细阐述),即移动的实际位数为:j - next[j],且此值大于等于1。 很快,你也会意识到next 数组各值的含义:若k=next[j],代表模式串P中当前字符之前的字符串中,最前面的k个字符和j之前的最后k个字符是一样的。
    如果用数学公式来表示是这样的:
    P[0 ~ k-1] == P[j-k ~ j-1]

    此也意味着在某个字符匹配失败时,该字符对应的next 值会告诉你下一步匹配中,模式串应该跳到哪个位置(跳到next [j] 的位置)。如果next [j] 等于0或-1,则跳到模式串的开头字符,若next [j] = k 且 k > 0,代表下次匹配跳到j 之前的某个字符,而不是跳到开头,且具体跳过了k 个字符。

    继续拿之前的例子来说,当S[10]跟P[6]匹配失败时,KMP不是跟暴力匹配那样简单的把模式串右移一位,而是执行第②条指令:“如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]”,即j 从6变到2(后面我们将求得P[6],即字符D对应的next 值为2),所以相当于模式串向右移动的位数为j - next[j](j - next[j] =6-2 = 4)。

    向右移动4位后,S[10]跟P[2]继续匹配。为什么要向右移动4位呢,因为移动4位后,模式串中又有个“AB”可以继续跟S[8]S[9]对应着,从而不用让i 回溯。相当于在除去字符D的模式串子串中寻找相同的前缀和后缀,然后根据前缀后缀求出next 数组,最后基于next 数组进行匹配(不关心next 数组是怎么求来的,只想看匹配过程是咋样的,可直接跳到下文3.3.4节)。

    如何求next数组
    由上文,我们已经知道,字符串“ABCDABD”各个前缀后缀的最大公共元素长度分别为:

    而且,根据这个表可以得出下述结论:

    失配时,模式串向右移动的位数为:已匹配字符数- 失配字符的上一位字符所对应的最大长度值

    上文利用这个表和结论进行匹配时,我们发现,当匹配到一个字符失配时,其实没必要考虑当前失配的字符,更何况我们每次失配时,都是看的失配字符的上一位字符对应的最大长度值。如此,便引出了next 数组。

    给定字符串“ABCDABD”,可求得它的next 数组如下:

    把next 数组跟之前求得的最大长度表对比后,不难发现,next 数组相当于“最大长度值” 整体向右移动一位,然后初始值赋为-1。意识到了这一点,你会惊呼原来next 数组的求解竟然如此简单:就是找最大对称长度的前缀后缀,然后整体右移一位,初值赋为-1(当然,你也可以直接计算某个字符对应的next值,就是看这个字符之前的字符串中有多大长度的相同前缀后缀)。
    换言之,对于给定的模式串:ABCDABD,它的最大长度表及next 数组分别如下:

    展开全文
  • JS常见算法小总结

    万次阅读 多人点赞 2019-05-14 16:23:21
    今天与大家一起来测试一下常用算法的性能解析: 首先我们创建一个含有十万个数组的数组用来测试: let array = []; for (let i = 0; i < 100000; i++) { array.push(i) } 接下来我们一起分析各个算法的性能: ...

    首先我们创建一个含有十万个数字的数组:

    let array = [];
    for (let i = 0; i < 100000; i++) {
    	array.push(i)
    }
    

    接下来我们一起分析各个算法的性能:

    首先来测试冒泡排序:
    function bubbleSort(arr) {
    	for(let i = 0; i < arr.length; i++) {
    		for(let j = 0; j < arr.length - i - 1; j++) {
    			if(arr[j] > arr[j+1]) {
    				let temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    		}
    	}
    	return arr;
    }
    console.time()
    bubbleSort(array);
    console.timeEnd()
    

    在这里插入图片描述
    可以看到冒泡排序的性能很差。




    接下来再来测试选择排序的性能:

    function selectionSort(arr) {
    	let len = arr.length;
    	let minIndex, temp;
    	for(let i = 0; i < len - 1; i++) {
    		minIndex = i;
    		for(var j = i + 1; j < len; j++) {
    			if (arr[j] < arr[minIndex]) {
    				minIndex = j;
    			}
    		}
    		temp = arr[i];
    		arr[i] = arr[minIndex];
    		arr[minIndex] = temp;
    	}
    	return arr;
    }
    console.time()
    selectionSort(array)
    console.timeEnd()
    

    在这里插入图片描述
    可以看到比冒泡排序快了一倍。




    我们再来测试一下插入排序的性能:

    
    //插入排序 过程就像你拿到一副扑克牌然后对它排序一样
    function insertionSort(arr) {
    	let len = arr.length;
    	let preIndex, current;
    	// 我们认为arr[0]已经被排序,所以i从1开始
    	for (let i = 1; i < len; i++) {
    		preIndex = i - 1;
    		current = arr[i];
    		while (preIndex >= 0 && arr[preIndex] > current) {
    			arr[preIndex + 1] = arr[preIndex];
    			preIndex--;
    		}
    		arr[preIndex + 1] = current;
    	}
    	return arr;
    }
    console.time()
    insertionSort(array)
    console.timeEnd()
    

    在这里插入图片描述
    ?????????????????????????????
    才2.96ms????

    我弄错了???在测试一下!!!结果还是这个时间左右。如果你认为这个是最快其实就误解了,因为我们现在数组里面的值刚刚好是从小到大排序的所以它才会这么快,如果对我们的这个数组做个反转再来使用插入排序的话,插入排序就会很慢很慢。

    当目标是升序排序,最好情况是序列本来已经是升序排序,那么只需比较n-1次,时间复杂度O(n)。最坏情况是序列本来是降序排序,那么需比较n(n-1)/2次,时间复杂度O(n^2)。所以平均来说,插入排序的时间复杂度是O(n^2)。显然,次方级别的时间复杂度代表着插入排序不适合数据特别多的情况,一般来说插入排序适合小数据量的排序。

    二分查找

    function binary_search(arr, l, r, v) {
    	if (l > r) {
    		return -1;
    	}
    	let m = parseInt((l + r) / 2);
    	if (arr[m] == v) {
    		return m;
    	} else if (arr[m] < v) {
    		return binary_search(arr, m + 1, r, v);
    	} else {
    		return binary_search(arr, l, m - 1, v);
    	}
    }
    

    将二分查找运用到之前的插入排序中,形成二分插入排序。




    接下来是快速排序

    function qSort(arr) {
    	//声名并初始化左边的数组和右边的数组
    	let left = [], right = [];
    	// 使用数组第一个元素作为基准值
    	let base = arr[0];
    	//当数组长度只有1或者为空时,直接返回数组,不需要排序
    	if (arr.length <= 1) return arr;
    	//进行遍历
    	for (let i = 1, len = arr.length; i < len; i++) {
    		if (arr[i] <= base) {
    			//如果小于基准值,push到左边的数组
    			left.push(arr[i])
    		} else {
    		//如果大于基准值,push到右边的数组
    			right.push(arr[i]);
    		}
    	}
    	//递归并且合并数组元素
    	return [...qSort(left), base, ...qSort(right)];
    }
    

    补充:

    在这段代码中,我们可以看到,这段代码实现了通过pivot区分左右部分,然后递归的在左右部分继续取pivot排序,实现了快速排序的文本描述,也就是说该的算法实现本质是没有问题的。

    虽然这种实现方式非常的易于理解。不过该实现也是有可以改进的空间,在这种实现中,我们发现在函数内定义了left/right两个数组存放临时数据。随着递归的次数增多,会定义并存放越来越多的临时数据,需要Ω(n)的额外储存空间。

    因此,像很多算法介绍中,都使用了原地(in-place)分区的版本去实现快速排序,我们先介绍什么是原地分区算法。

    原地(in-place)分区算法描述

    1. 从数列中挑选一个元素,称为“基准”(pivot),数组第一个元素的位置作为索引。
    2. 遍历数组,当数组数字小于或者等于基准值,则将索引位置上的数与该数字进行交换,同时索引+1。
    3. 将基准值与当前索引位置进行交换。

    通过以上3个步骤,就将以基准值为中心,数组的左右两侧数字分别比基准值小或者大了。这个时候在递归的原地分区,就可以得到已排序后的数组。

    原地分区算法实现

    //交换数组元素位置
    function swap(array, i, j) {
    	let temp = array[i];
    	array[i] = array[j];
    	array[j] = temp;
    }
    
    function partition(array, left, right) {
    	let index = left;
    	let pivot = array[right];  //取最后一个数字当做基准值,这样方便遍历
    	for (let i = left; i < right; i++) {
    		if (array[i] <= pivot) {
    			swap(array, index, i);
    			index++;
    		}
    	}
    	swap(array, right, index);
    	return index;
    }
    

    因为我们需要递归的多次原地分区,同时,又不想额外的地址空间所以,在实现分区算法的时候会有3个参数,分别是原数组array,需要遍历的数组起点left以及需要遍历的数组终点right
    最后返回一个已经排好序的index值用于下次递归,该索引对应的值一定比索引左侧的数组元素小,比所有右侧的数组元素大。

    再次基础上我们还是可以进一步的优化分区算法,我们发现 <=pivot可以改为<pivot,这样可以减少一次交换。

    原地分区版快速排序实现

    function quickSort(array) {
    	function swap(array, i, j) {
    		let temp = array[i];
    		array[i] = array[j];
    		array[j] = temp;
    	}
    	function partition(array, left, right) {
    		let index = left;
    		let pivot = array[right];	//取最后一个数字当做基准值,这样方便遍历
    		for (let i = left; i < right; i++) {
    			if (array[i] < pivot) {
    				swap(array, index, i);
    				index++;
    			}
    		}
    		swap(array, right, index);
    		return index;
    	}
    	function sort(array, left, right) {
    		if (left > right) {
    			return;
    		}
    		let storeIndex = partition(array, left, right);
    		sort(array, left, storeIndex - 1);
    		sort(array, storeIndex + 1, right);
    	}
    	sort(array, 0, array.length - 1);
    	return array;
    }
    
    展开全文
  • 人工智能之机器学习常见算法

    万次阅读 多人点赞 2016-05-22 15:47:54
    摘要之前一直对机器学习很感兴趣,一直没时间去研究,今天刚好是...这里IT经理网为您总结一下常见的机器学习算法,以供您在工作和学习中参考。 机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有

    这里写图片描述

    摘要

    之前一直对机器学习很感兴趣,一直没时间去研究,今天刚好是周末,有时间去各大技术论坛看看,刚好看到一篇关于机器学习不错的文章,在这里就分享给大家了.
    机器学习无疑是当前数据分析领域的一个热点内容。很多人在平时的工作中都或多或少会用到机器学习的算法。这里IT经理网为您总结一下常见的机器学习算法,以供您在工作和学习中参考。
    这里写图片描述
    机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有些算法又是从其他算法中延伸出来的。这里,我们从两个方面来给大家介绍,第一个方面是学习的方式,第二个方面是算法的类似性。
    这里写图片描述

    学习方式

    根据数据类型的不同,对一个问题的建模有不同的方式。在机器学习或者人工智能领域,人们首先会考虑算法的学习方式。在机器学习领域,有几种主要的学习方式。将算法按照学习方式分类是一个不错的想法,这样可以让人们在建模和算法选择的时候考虑能根据输入数据来选择最合适的算法来获得最好的结果。

    监督式学习:

    这里写图片描述

    在监督式学习下,输入数据被称为“训练数据”,每组训练数据有一个明确的标识或结果,如对防垃圾邮件系统中“垃圾邮件”“非垃圾邮件”,对手写数字识别中的“1“,”2“,”3“,”4“等。在建立预测模型的时候,监督式学习建立一个学习过程,将预测结果与“训练数据”的实际结果进行比较,不断的调整预测模型,直到模型的预测结果达到一个预期的准确率。监督式学习的常见应用场景如分类问题和回归问题。常见算法有逻辑回归(Logistic Regression)和反向传递神经网络(Back Propagation Neural Network)

    非监督式学习:

    这里写图片描述

    在非监督式学习中,数据并不被特别标识,学习模型是为了推断出数据的一些内在结构。常见的应用场景包括关联规则的学习以及聚类等。常见算法包括Apriori算法以及k-Means算法。

    半监督式学习:

    这里写图片描述

    在此学习方式下,输入数据部分被标识,部分没有被标识,这种学习模型可以用来进行预测,但是模型首先需要学习数据的内在结构以便合理的组织数据来进行预测。应用场景包括分类和回归,算法包括一些对常用监督式学习算法的延伸,这些算法首先试图对未标识数据进行建模,在此基础上再对标识的数据进行预测。如图论推理算法(Graph Inference)或者拉普拉斯支持向量机(Laplacian SVM.)等。

    强化学习:

    这里写图片描述

    在这种学习模式下,输入数据作为对模型的反馈,不像监督模型那样,输入数据仅仅是作为一个检查模型对错的方式,在强化学习下,输入数据直接反馈到模型,模型必须对此立刻作出调整。常见的应用场景包括动态系统以及机器人控制等。常见算法包括Q-Learning以及时间差学习(Temporal difference learning)

    在企业数据应用的场景下, 人们最常用的可能就是监督式学习和非监督式学习的模型。 在图像识别等领域,由于存在大量的非标识的数据和少量的可标识数据, 目前半监督式学习是一个很热的话题。 而强化学习更多的应用在机器人控制及其他需要进行系统控制的领域。

    算法类似性

    根据算法的功能和形式的类似性,我们可以把算法分类,比如说基于树的算法,基于神经网络的算法等等。当然,机器学习的范围非常庞大,有些算法很难明确归类到某一类。而对于有些分类来说,同一分类的算法可以针对不同类型的问题。这里,我们尽量把常用的算法按照最容易理解的方式进行分类。

    回归算法:

    这里写图片描述

    回归算法是试图采用对误差的衡量来探索变量之间的关系的一类算法。回归算法是统计机器学习的利器。在机器学习领域,人们说起回归,有时候是指一类问题,有时候是指一类算法,这一点常常会使初学者有所困惑。常见的回归算法包括:最小二乘法(Ordinary Least Square),逻辑回归(Logistic Regression),逐步式回归(Stepwise Regression),多元自适应回归样条(Multivariate Adaptive Regression Splines)以及本地散点平滑估计(Locally Estimated Scatterplot Smoothing)

    基于实例的算法

    这里写图片描述

    基于实例的算法常常用来对决策问题建立模型,这样的模型常常先选取一批样本数据,然后根据某些近似性把新数据与样本数据进行比较。通过这种方式来寻找最佳的匹配。因此,基于实例的算法常常也被称为“赢家通吃”学习或者“基于记忆的学习”。常见的算法包括 k-Nearest Neighbor(KNN), 学习矢量量化(Learning Vector Quantization, LVQ),以及自组织映射算法(Self-Organizing Map , SOM)

    正则化方法

    这里写图片描述

    正则化方法是其他算法(通常是回归算法)的延伸,根据算法的复杂度对算法进行调整。正则化方法通常对简单模型予以奖励而对复杂算法予以惩罚。常见的算法包括:Ridge Regression, Least Absolute Shrinkage and Selection Operator(LASSO),以及弹性网络(Elastic Net)。

    决策树学习

    这里写图片描述

    决策树算法根据数据的属性采用树状结构建立决策模型, 决策树模型常常用来解决分类和回归问题。常见的算法包括:分类及回归树(Classification And Regression Tree, CART), ID3(Iterative Dichotomiser 3), C4.5, Chi-squared Automatic Interaction Detection(CHAID), Decision Stump, 随机森林(Random Forest), 多元自适应回归样条(MARS)以及梯度推进机(Gradient Boosting Machine, GBM)

    贝叶斯方法

    这里写图片描述

    贝叶斯方法算法是基于贝叶斯定理的一类算法,主要用来解决分类和回归问题。常见算法包括:朴素贝叶斯算法,平均单依赖估计(Averaged One-Dependence Estimators, AODE),以及Bayesian Belief Network(BBN)。

    基于核的算法

    这里写图片描述

    基于核的算法中最著名的莫过于支持向量机(SVM)了。 基于核的算法把输入数据映射到一个高阶的向量空间, 在这些高阶向量空间里, 有些分类或者回归问题能够更容易的解决。 常见的基于核的算法包括:支持向量机(Support Vector Machine, SVM), 径向基函数(Radial Basis Function ,RBF), 以及线性判别分析(Linear Discriminate Analysis ,LDA)等

    聚类算法

    这里写图片描述
    聚类,就像回归一样,有时候人们描述的是一类问题,有时候描述的是一类算法。聚类算法通常按照中心点或者分层的方式对输入数据进行归并。所以的聚类算法都试图找到数据的内在结构,以便按照最大的共同点将数据进行归类。常见的聚类算法包括 k-Means算法以及期望最大化算法(Expectation Maximization, EM)。

    关联规则学习

    这里写图片描述
    关联规则学习通过寻找最能够解释数据变量之间关系的规则,来找出大量多元数据集中有用的关联规则。常见算法包括 Apriori算法和Eclat算法等。

    人工神经网络

    这里写图片描述
    人工神经网络算法模拟生物神经网络,是一类模式匹配算法。通常用于解决分类和回归问题。人工神经网络是机器学习的一个庞大的分支,有几百种不同的算法。(其中深度学习就是其中的一类算法,我们会单独讨论),重要的人工神经网络算法包括:感知器神经网络(Perceptron Neural Network), 反向传递(Back Propagation), Hopfield网络,自组织映射(Self-Organizing Map, SOM)。学习矢量量化(Learning Vector Quantization, LVQ)

    深度学习

    这里写图片描述

    深度学习算法是对人工神经网络的发展。 在近期赢得了很多关注, 特别是百度也开始发力深度学习后, 更是在国内引起了很多关注。 在计算能力变得日益廉价的今天,深度学习试图建立大得多也复杂得多的神经网络。很多深度学习的算法是半监督式学习算法,用来处理存在少量未标识数据的大数据集。常见的深度学习算法包括:受限波尔兹曼机(Restricted Boltzmann Machine, RBN), Deep Belief Networks(DBN),卷积网络(Convolutional Network), 堆栈式自动编码器(Stacked Auto-encoders)。

    降低维度算法

    这里写图片描述

    像聚类算法一样,降低维度算法试图分析数据的内在结构,不过降低维度算法是以非监督学习的方式试图利用较少的信息来归纳或者解释数据。这类算法可以用于高维数据的可视化或者用来简化数据以便监督式学习使用。常见的算法包括:主成份分析(Principle Component Analysis, PCA),偏最小二乘回归(Partial Least Square Regression,PLS), Sammon映射,多维尺度(Multi-Dimensional Scaling, MDS), 投影追踪(Projection Pursuit)等。

    集成算法:

    这里写图片描述
    集成算法用一些相对较弱的学习模型独立地就同样的样本进行训练,然后把结果整合起来进行整体预测。集成算法的主要难点在于究竟集成哪些独立的较弱的学习模型以及如何把学习结果整合起来。这是一类非常强大的算法,同时也非常流行。常见的算法包括:Boosting, Bootstrapped Aggregation(Bagging), AdaBoost,堆叠泛化(Stacked Generalization, Blending),梯度推进机(Gradient Boosting Machine, GBM),随机森林(Random Forest)。

    结束

    在之后的时间里我会给大家一一介绍这些算法的具体实现.敬请大家期待,大家想一起跟我交流技术,可以关注我的个人公众号.
    源码下载地址:

    源码下载地址

    展开全文
  • 算法描述---伪代码

    千次阅读 2017-12-15 14:33:44
    算法描述  算法描述是指对设计出的算法,用一种方式进行详细的描述,以便与人交流。描述可以使用自然语言、伪代码,也可使用程序流程图,但描述的结果必须满足算法的五个特征。 使用自然语言描述算法显然很有...
  • 人工智能常见算法简介

    万次阅读 2019-02-15 13:17:32
    人工智能的三大基石—算法、数据和计算能力,算法作为其他之一,是非常重要的,那么人工智能都会涉及哪些算法呢?不同算法适用于哪些场景呢? 一、按照模型训练方式不同可以分为监督学习(Supervised Learning),...
  • 二叉树的常见算法

    万次阅读 多人点赞 2018-08-05 16:28:21
    二叉树的遍历算法 二叉树的遍历可分为三种:先序遍历,中序遍历和后序遍历。 按照惯例,左孩子优先于右孩子,那么: - 先序遍历指的就是先访问本节点,再访问该节点的左孩子和右孩子; - 中序遍历指的就是...
  • 常见算法时间复杂度

    千次阅读 2015-04-09 16:51:44
    同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 一、时间复杂度 (1)时间...
  • 机器学习常见算法分类,算法优缺点汇总

    万次阅读 多人点赞 2017-04-14 12:08:13
    本文为您总结一下常见的机器学习算法,以供您在工作和学习中参考。  机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有些算法又是从其他算法中延伸出来的。这里,我们从两个方面来给大家...
  • 基于平时对【算法】的了解,特写此文来整理一下常见算法。注意,此文不对算法的具体细节做深究,仅供基础入门学习。限于篇幅原因,本文先介绍【对称加密算法】。 对称加密算法  对称加密算法,顾名思义,就是...
  • 机器学习常见算法

    千次阅读 2018-08-21 21:47:27
    1. 线性回归 线性回归可能是统计学和机器学习中最知名和最易...线性回归用一个等式表示,通过找到输入变量的特定权重(B),来描述输入变量(x)与输出变量(y)之间的线性关系。   Linear Regression 举例:...
  • 算法描述

    千次阅读 2012-08-26 21:04:59
    数据的运算通过算法(Algorithm)描述,讨论算法是数据结构课程的重要内容之一。 1.算法  非形式地说,算法是任意一个良定义的计算过程。它以一个或多个值作为输入,并产生一个或多个值作为输出。 (1)一个算法...
  • 机器学习常见算法分类汇总

    千次阅读 2015-07-24 09:12:16
    本文为您总结一下常见的机器学习算法,以供您在工作和学习中参考。机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有些算法又是从其他算法中延伸出来的。这里,我们从两个方面来给大家介绍,第一...
  • 实际项目中的常见算法

    千次阅读 2016-05-20 16:52:29
    Emanuele Viola在Stackexchange上提了这样的一个问题,他希望有人能够列举一些目前软件、硬件中正在使用的算法的实际案例来证明算法的重要性,对于大家可能给到的回答,他还提出了几点要求: 1、使用这些算法的...
  • JS 常见算法的解析和代码实现

    千次阅读 2020-08-18 16:56:17
    JS 常见算法的解析和代码实现 一、欧几里得定理(辗转相除法) 1. 条件 求 A 和 B 的最大公约数,A 和 B 都是大于等于 0 的整数。 2. 应用场景 欧几里得定理,在数学上,用来计算两个非负整数的最大公约数。 辗转...
  • 论文中的算法描述 By 薛磊

    千次阅读 2015-02-08 23:02:00
    薛磊从《Writing for computer science》中整理了一份PPT,介绍几种常见算法描述方法。 下面是下载链接: Algorithms_writing.pdf 转载于:https://www.cnblogs.com/yulele/p/4280633.html...
  • 常见聚类算法总结

    万次阅读 2018-09-07 17:12:55
    1.常见算法 1.原型聚类 “原型”是指样本空间中具有代表性的店。此类算法假设聚类结构能够通过一组原型刻画,通常情形下,算法先对原型进行初始化,然后对原型进行迭代更新求解。–西瓜书 (1).K均值聚类(K-...
  • 8种常见算法比较

    万次阅读 2016-08-09 17:42:38
    8种常见机器学习算法比较 2016-08-04 17:46 转载 陈圳 0条评论 雷锋网(搜索“雷锋网”公众号关注)按:本文转自刘志伟责编,在机器学习中选择一个恰当的算法十分重要,文中主要介绍了8种计算机算法...
  • 常见分类算法

    万次阅读 2018-05-17 11:38:48
    常见分类算法 朴素贝叶斯网络、贝叶斯信念网络、随机森林、k-最近邻分类 云聚类算法引擎 k-Means、Canopy、Fuzzy K-Means、Mean Shift 云关联规则算法引起 FP-Growth关联规则 云智能推荐算法引擎 基于内存的...
  • 文章目录1 分治算法的一般性描述1.1 分支算法的时间分析1.2 两类常见的递推方程与求解方法2 总结 1 分治算法的一般性描述 设分治算法为:Divide-and-Conquer§ 设计要点 原问题可以划分或者规约为规模较小的...
  • 深度学习常见算法的介绍和比较

    万次阅读 多人点赞 2018-02-08 22:00:06
    很多人都有误解,以为深度...关于深度学习的理论推导,太大太复杂,一些常见的深度学习算法本人也是模模糊糊的,看过好多次的,隔断时间就会忘记,现在对其系统的整理一下(从历史,致命问题出发,再看具体算法的思想,
  • 人工智能—机器学习常见算法

    千次阅读 2018-01-29 10:00:16
    摘要 之前一直对机器学习很感兴趣,一直没时间去研究,今天刚好是周末,...这里IT经理网为您总结一下常见的机器学习算法,以供您在工作和学习中参考。    机器学习的算法很多。很多时候困惑人们都是,很多算法是一
  • 大数据常见算法

    千次阅读 2016-09-02 16:40:53
    (2) 请给出主要的处理流程,算法,以及算法的复杂度。 方案1:采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。 14. 一共有N个机器,每个机器上有...
  • 常见的7种排序算法

    万次阅读 多人点赞 2018-06-10 11:37:21
    则冒泡排序的具体过程可以描述为:首先从数组的第一个元素开始到数组最后一个元素为止,对数组中相邻的两个元素进行比较,如果位于数组左端的元素大于数组右端的元素,则交换这两个元素在数组中的位置,此时数组最...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 220,799
精华内容 88,319
关键字:

常见的算法描述