精华内容
下载资源
问答
  • 文章目录1 算法的研究内容2 算法设计的两个例子2.1 调度问题2.2 算法设计的步骤2.3 投资问题3 总结 在学习算法涉及与分析的内容之前,先了解一下算法所涉及的几个大块的内容,方便以后学习。 1 算法的研究内容 算法...


    在学习算法涉及与分析的内容之前,先了解一下算法所涉及的几个大块的内容,方便以后学习。

    1 算法的研究内容

    • 算法的研究内容主要包括三点:
    1. 计算复杂性理论
    2. 问题复杂度概念
    3. 算法设计与分析

    其中我们主要学习的内容是算法的设计与分析。

    在学习算法的过程中,还需要学习相关的概念:

    1. 算法的伪码表示
    2. 算法及其时间复杂度的定义
    3. 几类重要函数的性质
    4. 有关函数渐进的届的定理
    5. 时间复杂度函数的表示:函数渐进的界

    以上五点会在后面的文章中逐一学习。

    2 算法设计的两个例子

    2.1 调度问题

    • 问题:有n项任务,每项任务加工时间已知,从 0时刻开始陆续安排到一台机器上加工,每个任务的完成时间是从 0 时刻到任务加工截止的时间。
    • 求:总完成时间 最短的安排方案(所有任务完成时间之和)。

    实例:
    任务集 S = {1, 2, 3, 4, 5},
    加工时间: t1=3, t2=8, t3=5, t4=10, t5=15

    • 贪心法的解:

    算法:按加工时间(3,8,5,10,15) 从小到大安排

    解:加工产品的顺序:1, 3, 2, 4, 5 。

    https://raw.githubusercontent.com/Lyy0217/CSLN-Pic/master/01-%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90pic/1560500922461.png

    总的完成时间为:

    t = 3+(3+5)+(3+5+8)+(3+5+8+10)+(3+5+8+10+15)
    = 3×5 + 5×4 + 8×3 + 10×2 + 15
    = 94

    (注意规律)

    针对上面的加工调度问题,在数学中有一整套建模的流程来求解。

    问题建模:

    1. 输入:任务集:S={1,2,3,…,n},第j项任务加工时间:tj \in Z+ , j=1,2…,n
    2. 输出:调度I,S的排列为:i1,i2,…,in
    3. 目标函数:I的完成时间。t(I)=k=1N(nk+1)tik\sum_{k=1}^N (n-k+1)t_{i_{k}}
    4. 解 I* :使得t(I*)达到最小,即:t(I *)=min{t(I) | I为S的排列}

    对于上述调度问题的贪心算法,对于所有输入实例都得到最优解,可以给出如下的证明过程:

    证明:假设调度f的第i,j项任务相邻且有逆序,即ti > tj ,交换任务i和j得到调度g,

    在算法的设计过程中,各种各样的算法设计都需要有严格的证明验证所有实例都可以通过该算法达到最终的解。上面解决调度问题的时候,是凭直觉来使用贪心算法,但是直觉往往不正确。如下面的例子。

    反例:

    有4 件物品要装入背包, 物品重量和价值如下:

    标号 1 2 3 4
    重量 wi 3 4 5 2
    价值 vi 7 9 9 2

    背包重量限制是 6,问如何选择物品,使得不超重的情况下装入背包的物品价值达到最大?

    直觉的解法是贪心算法:单位重量价值大的优先,总重量不超过6.

    按照V i W i \frac{V~i~}{W~i~} 从大到小排序,1,2,3,4

    73\frac{7}{3} >94\frac{9}{4}> 95\frac{9}{5} >22\frac{2}{2}

    • 贪心法的解: { 1, 4 },重量 5,价值为 9
    • 更好的解: { 2, 4 },重量 6,价值 11

    2.2 算法设计的步骤

    所以在进行一个算法的设计时,需要以下几个步骤:

    1. 问题建模
    2. 选择什么算法,如何描述这个算法?
    3. 这个算法是否对所有实例都得到最优解?如何证明?
    4. 如果不是,能否找到反例

    每一个算法的设计,都需要遵循上述四个规则。

    2.3 投资问题

    • 问题:m元钱,投资n个项目,效益函数fi (x),表示第i个项目投资x元钱的效益,i=1,2,…,n。
    • 求:如何分配,每个项目的钱数,使得总效益最大。

    实例:5 万元,投资给 4 个项目,效益函数:

    x f1(x) f2(x) f3(x) f4(x)
    0 0 0 0 0
    1 11 0 2 20
    2 12 5 10 21
    3 13 10 30 22
    4 14 15 32 23
    5 15 20 40 24

    首先对这个问题进行数学建模:

    • 输入:n,m,fi (x),i=1,2,…,n,x = 1,2, …, m 。
    • 解:n维向量<x1, x2, … , xn >,xi 是第i个项目的钱数,使得下述条件满足:

    目标函数:maxi=1nfi(x)\sum_{i=1}^n f_i (x)

    约束条件:i=1nxi=m\sum_{i=1}^n x_i =m ,xi \in n;

    上述就是一个数学的建模过程,最终的算法设计就是针对上述数学模型进行求解域优化。

    在我们学习算法设计之前,先给出这道题的一个蛮力算法:

    1. 对所有满足下述条件的向量<x1,x2,…,xn>

      x1+ x2 + … + xn = m ; xi 为非负整数, i = 1, 2 , …, n 。

    2. 计算相应的效益:

      f1(x1) + f2(x2) + … + fn(xn)

    从中确认效益最大的向量。

    实例计算:

    https://raw.githubusercontent.com/Lyy0217/CSLN-Pic/master/01-%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90pic/1561486060934.png

    解: s=<1,0,3,1>,
    最大效益: 11+30+20 = 61

    以上就是使用蛮力算法得出的额结果,结果肯定是对的,但是效率肯定不高。

    • 蛮力算法的效率:

    方程 x1 + x2 + … + xn = m 的非负整数解
    < x1, x2, …, xn > 的个数估计:

    可行解表示成 0-1 序列: m 个1,n-1个 0

    https://raw.githubusercontent.com/Lyy0217/CSLN-Pic/master/01-%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90pic/04.png

    例如:n=4,m=7。可行解的一个为:<1, 2, 3, 1> ⇔ 序列 1 0 1 1 0 1 1 1 0 1

    该解得序列的个数是输入规模的指数函数:

    C(m+n-1,m)

    =(m+n1)!m!(n1)!\frac{(m+n-1)!}{m! (n-1)!}

    = Ω ((1+ε )m+n-1)

    指数级是一个很大的数量级!!!有没有更好的算法? 在后面的学习中,会学习到更好的算法。

    3 总结

    问题求解的关键:

    1. 建模:对输入参数和解给出形式化或者半形式化的描述
    2. 设计算法:采用什么算法设计技术?以及它的正确性:是否对所有实例都得到正确的解?
    3. 分析算法:效率
    展开全文
  • 算法

    万次阅读 2018-02-08 00:13:09
    1.算法定义 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出...

    1.算法定义

    算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

    一个算法应该具有以下七个重要的特征:
    ①有穷性(Finiteness):算法的有穷性是指算法必须能在执行有限个步骤之后终止;
    ②确切性(Definiteness):算法的每一步骤必须有确切的定义;
    ③输入项(Input):一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输 入是指算法本身定出了初始条件;
    ④输出项(Output):一个算法有一个或多个输出,以反映对输入数据加工后的结果。没 有输出的算法是毫无意义的;
    ⑤可行性(Effectiveness):算法中执行的任何计算步骤都是可以被分解为基本的可执行 的操作步,即每个计算步都可以在有限时间内完成(也称之为有效性);
    ⑥高效性(High efficiency):执行速度快,占用资源少;
    ⑦健壮性(Robustness):对数据响应正确。

    2. 时间复杂度

    计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间,时间复杂度常用大O符号(大O符号(Big O notation)是用于描述函数渐进行为的数学符号。更确切地说,它是用另一个(通常更简单的)函数来描述一个函数数量级的渐近上界。在数学中,它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项;在计算机科学中,它在分析算法复杂性的方面非常有用。)表述,使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。

    大O,简而言之可以认为它的含义是“order of”(大约是)。

    无穷大渐近

    大O符号在分析算法效率的时候非常有用。举个例子,解决一个规模为 n 的问题所花费的时间(或者所需步骤的数目)可以被求得:T(n) = 4n^2 - 2n + 2。 当 n 增大时,n^2; 项将开始占主导地位,而其他各项可以被忽略——举例说明:当 n = 500,4n^2; 项是 2n 项的1000倍大,因此在大多数场合下,省略后者对表达式的值的影响将是可以忽略不计的。

    3.时间复杂度计算方法

    1.一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。
    一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

    2.一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))。随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。
    在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度T(n)=O(f(n))。

    3.常见的时间复杂度
    按数量级递增排列,常见的时间复杂度有:
    常数阶O(1), 对数阶O(log2n), 线性阶O(n), 线性对数阶O(nlog2n), 平方阶O(n^2), 立方阶O(n^3),…, k次方阶O(n^k), 指数阶O(2^n) 。

    其中,
    1.O(n),O(n^2), 立方阶O(n^3),…, k次方阶O(n^k) 为多项式阶时间复杂度,分别称为一阶时间复杂度,二阶时间复杂度。。。。
    2.O(2^n),指数阶时间复杂度,该种不实用
    3.对数阶O(log2n), 线性对数阶O(nlog2n),除了常数阶以外,该种效率最高
    例:算法:
      for(i=1;i<=n;++i)
      {
         for(j=1;j<=n;++j)
         {
             c[ i ][ j ]=0; //该步骤属于基本操作 执行次数:n^2
              for(k=1;k<=n;++k)
                   c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数:n^3
         }
      }
      则有 T(n)= n^2+n^3,根据上面括号里的同数量级,我们可以确定 n^3为T(n)的同数量级
      则有f(n)= n^3,然后根据T(n)/f(n)求极限可得到常数c
      则该算法的 时间复杂度:T(n)=O(n^3)
    

    4.讨论

    定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

    当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。

    我们常用大O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者。

    此外,一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。

    “大O记法”:在这种描述中使用的基本参数是 n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order),比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时,运行时间至多将以正比于 f(n)的速度增长。

    这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差异。例如,一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。

    O(1)
    
    Temp=i;i=j;j=temp;                    
    
    以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
    
    O(n^2)
    
    2.1. 交换i和j的内容
         sum=0;                 (一次)
         for(i=1;i<=n;i++)       (n次 )
            for(j=1;j<=n;j++) (n^2次 )
             sum++;       (n^2次 )
    解:T(n)=2n^2+n+1 =O(n^2)
    
    2.2.   
        for (i=1;i<n;i++)
        {
            y=y+1;         ①   
            for (j=0;j<=(2*n);j++)    
               x++;        ②      
        }         
    解: 语句1的频度是n-1
              语句2的频度是(n-1)*(2n+1)=2n^2-n-1
              f(n)=2n^2-n-1+(n-1)=2n^2-2
              该程序的时间复杂度T(n)=O(n^2).         
    
    O(n)      
                                                          
    2.3.
        a=0;
        b=1;                      ①
        for (i=1;i<=n;i++) ②
        {  
           s=a+b;    ③
           b=a;     ④  
           a=s;     ⑤
        }
    解:语句1的频度:2,        
               语句2的频度: n,        
              语句3的频度: n-1,        
              语句4的频度:n-1,    
              语句5的频度:n-1,                                  
              T(n)=2+n+3(n-1)=4n-1=O(n).
                                                                                                     
    O(log2n )
    
    2.4.
         i=1;       ①
        while (i<=n)
           i=i*2; ②
    解: 语句1的频度是1,  
              设语句2的频度是f(n),   则:2^f(n)<=n;f(n)<=log2n    
              取最大值f(n)= log2n,
              T(n)=O(log2n )
    
    O(n^3)
    
    2.5.
        for(i=0;i<n;i++)
        {  
           for(j=0;j<i;j++)  
           {
              for(k=0;k<j;k++)
                 x=x+2;  
           }
        }
    解:当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).
    

    我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 O(n^2),但期望时间是 O(nlogn)。通过每次都仔细地选择基准值,我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中,精心实现的快速排序一般都能以 (O(nlogn)时间运行。

    下面是一些常用的记法:
    访问数组中的元素是常数时间操作,或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n^3),因为算出每个元素都需要将n对 元素相乘并加到一起,所有元素的个数是n^2。
    指数时间算法通常来源于需要求出所有可能结果。例如,n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。指数算法一般说来是太复杂了,除非n的值非常小,因为,在 这个问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题 (如著名的“巡回售货员问题” ),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况,通常应该用寻找近似最佳结果的算法替代之。

    5.常用排序

    这里写图片描述

    展开全文
  • 大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...

    大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。

    本文的逻辑顺序为
    1、最基本的朴素算法
    2、优化的KMP算法
    3、应算法需要定义的next值
    4、手动写出较短串的next值的方法
    5、最难理解的、足足有5行的代码的求next值的算法
    所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显不专业…

    一、问题描述

    给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。

    二、朴素算法

    最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例,一张动图模拟朴素算法:

    在这里插入图片描述
    这个算法简单,不多说,附上代码

    #include<stdio.h>
    int Index_1(char s[],int sLen,char p[],int pLen){//s为主串,sLen为主串元素个数,p为模式串,pLen为模式串的个数
        if(sLen<pLen)return 0;
        int i = 1,j = 1;
        while(i<=sLen && j<=pLen){
            if(s[i]==p[j]){i++;j++;}
            else{
                i = i-j+2;
                j = 1;
            }
        }
        if(j>pLen) return i-pLen;
        return 0;
    }
    void main(){
        char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
        char p[]={' ','a','b','a','a','b','c','a','c'};
        int sLen = sizeof(s)/sizeof(char)-1;
        int pLen = sizeof(p)/sizeof(char)-1;
        printf("%d",Index_1(s,sLen,p,pLen));
    }
    

    三、改进的算法——KMP算法

    朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。
    一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。
    朴素算法中,P的第j位失配,默认的把P串后移一位。
    但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?答案是肯定的。再看下面改进后的动图:
    在这里插入图片描述

    这个模拟过程即KMP算法,若没有看明白,继续往下看相应的解释,理解需要把P多移几位,然后回头再看一遍这个图就很明了了。

    相比朴素算法:
    朴素算法: 每次失配,S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1;T(n)=O(n*m)
    KMP算法: 每次失配,S串的索引i不动,P串的索引j定位到某个数。T(n)=O(n+m),时间效率明显提高

    而这“定位到某个数”,这个数就是接下来引入的next值。(实际上也就是P往后移多少位,换一种说法罢了:从上图中也可以看出,失配时固定i不变,令S[i]与P[某个数]对齐,实际上是P右移几位的另一种表达,只有为什么这么表达,当然是因为程序好写。)

    开——始——划——重——点!(图对逻辑关系比较好理解,但i和j的关系对后面求next的算法好理解!)

    • 比如,Pj处失配,绿色的是Pj,则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
      在这里插入图片描述

    • 假设P1…Pj-1中,P1…Pk-1与Pj-k+1…Pj-1是一一相等的,为了下面说的清楚,我们把这种关系叫做“首尾重合”
      在这里插入图片描述

    • 那么可以推出,P1…Pk-1与Si…Si+j-2
      在这里插入图片描述

    • 显然,接下来要做的就是把模式串右移了,移到哪里就不用多说了:
      在这里插入图片描述

    • 为了表示下一轮比较j定位的地方,我们将其定义为next[j],next[j]就是第j个元素前j-1个元素首尾重合部分个数加一,当然,为了能遍历完整,首尾重合部分的元素个数应取到最多,即next[j]应取尽量大的值,原因挺好理解的,可以想个例子模拟一下,会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即,对于字符串P,next[8]=4。如此,再看一下上面的动图是不是清楚了不少。

    • 最后,如果我们知道了一个字符串的next值,那么KMP算法也就很好懂了。相比朴素算法,当发生失配时,i不变,j=next[j]就好啦!接下来就是怎么确定next值了。

    四、手动写出一个串的next值

    我们规定任何一个串,next[1]=0。(不用next[0],与串的所有对应),仍是一张动图搞定问题:
    在这里插入图片描述
    这个扫一眼就能依次写出,会了这个方法,应付个期末考试没问题了。

    通过把next值“看”出来,我们再来分析next值,这就很容易得到超级有名的公式了,这个式子对后面的算法理解很重要!所以先要看懂这个式子,如果上面的内容通下来了,这个应该很容易看懂了:
    在这里插入图片描述

    五、求next的算法

    终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。

    int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
        next[1] = 0;
        int i = 1,j = 0;
        while(i<=cLen){
            if(j==0||ch[i]==ch[j]) next[++i] = ++j;
            else j = next[j];
        }
    }
    
    • 还是先由一般再推优化:
      直接求next[j+1](至于为什么是j+1,是为了和下面的对应)
      根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。
      不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序:
      if(P1…Pj-1 == P2…Pj) => next[j+1]=j
      else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
      else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2



      else if(P1P2 == Pj-1Pj) => next[j+1]=3
      else if(P1 == Pj-1) => next[j+1]=2
      else if(P1 != Pj-1) => next[j+1]=1

      每次前去尾1个,后掐头1个,直至得到next[j+1]

    • 再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组
      但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,
      ①next[j+1]的可能的最大值是多少(即从哪开始验证)
      ②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值)
      看一下的分析:

    1、next[j+1]的最大值为next[j]+1。
    因为:
    假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。
    如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+1
    2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]
    这里不好解释,直接看下面的流程分析及图解

    开——始——划——重——点!
    从头走一遍流程
    ①求next[j+1],设值为m
    已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-1
    如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则
    已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
    ⑤第二第三步联合得到:
    P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
    ⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推

    上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:
    1、要求next[k+1] 其中k+1=17
    在这里插入图片描述
    2、已知next[16]=8,则元素有以下关系:
    在这里插入图片描述
    3、如果P8=P16,则明显next[17]=8+1=9
    4、如果不相等,又若next[8]=4,则有以下关系

    在这里插入图片描述
    又加上2的条件知
    在这里插入图片描述
    主要是为了证明:
    在这里插入图片描述
    5、现在在判断,如果P16=P4则next[17]=4+1=5,否则,在继续递推
    6、若next[4]=2,则有以下关系
    在这里插入图片描述
    7、若P16=P2,则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0;遇到0时还没出结果,则递推结束,此时next[17]=1。最后,再返回看那5行算法,应该很容易明白了!

    展开全文
  • “无意中发现了一个巨牛的人工智能教程,忍不住分享一下给大家。教程不仅是零基础,通俗易懂,而且非常风趣幽默,像看... 基于内容的信息推荐方法的理论依据主要来自于信息检索和信息过滤,所谓的基于内容的推荐方法...

    “无意中发现了一个巨牛的人工智能教程,忍不住分享一下给大家。教程不仅是零基础,通俗易懂,而且非常风趣幽默,像看小说一样!觉得太牛了,所以分享给大家。点这里可以跳转到教程。”

    所谓推荐算法就是利用用户的一些行为,通过一些数学算法,推测出用户可能喜欢的东西。推荐算法主要分为两种

    1. 基于内容的推荐

         基于内容的信息推荐方法的理论依据主要来自于信息检索和信息过滤,所谓的基于内容的推荐方法就是根据用户过去的浏览记录来向用户推荐用户没有接触过的推荐项。主要是从两个方法来描述基于内容的推荐方法:启发式的方法和基于模型的方法。启发式的方法就是用户凭借经验来定义相关的计算公式,然后再根据公式的计算结果和实际的结果进行验证,然后再不断修改公式以达到最终目的。而对于模型的方法就是根据以往的数据作为数据集,然后根据这个数据集来学习出一个模型。一般的推荐系统中运用到的启发式的方法就是使用tf-idf的方法来计算,跟还有tf-idf的方法计算出这个文档中出现权重比较高的关键字作为描述用户特征,并使用这些关键字作为描述用户特征的向量;然后再根据被推荐项中的权重高的关键字来作为推荐项的属性特征,然后再将这个两个向量最相近的(与用户特征的向量计算得分最高)的项推荐给用户。在计算用户特征向量和被推荐项的特征向量的相似性时,一般使用的是cosine方法,计算两个向量之间夹角的cosine值。

     

    2.基于协同过滤的推荐

        基于协同过滤的推荐算法理论上可以推荐世界上的任何一种东西。图片、音乐、样样可以。 协同过滤算法主要是通过对未评分项进行评分 预测来实现的。不同的协同过滤之间也有很大的不同。

        基于用户的协同过滤算法: 基于一个这样的假设“跟你喜好相似的人喜欢的东西你也很有可能喜欢。”所以基于用户的协同过滤主要的任务就是找出用户的最近邻居,从而根据最近邻 居的喜好做出未知项的评分预测。这种算法主要分为3个步骤:

         一,用户评分。可以分为显性评分和隐形评分两种。显性评分就是直接给项目评分(例如给百度里的用户评分),隐形评分就是通过评价或是购买的行为给项目评分 (例如在有啊购买了什么东西)。

        二,寻找最近邻居。这一步就是寻找与你距离最近的用户,测算距离一般采用以下三种算法: 1.皮尔森相关系数。 2.余弦相似性。 3调整余弦相似性。 调整余弦 相似性似乎效果会好一些。

        三,推荐。产生了最近邻居集合后,就根据这个集合对未知项进行评分预测。把评分最高的N个项推荐给用户。 这种算法存在性能上的瓶颈,当用户数越来越多的时候,寻找最近邻居的复杂度也会大幅度的增长。

         因而这种算法无法满足及时推荐的要求。基于项的协同过滤解决了这个问题。 基于项的协同过滤算法 根基于用户的算法相似,只不过第二步改为计算项之间的相似度。由于项之间的相似度比较稳定可以在线下进行,所以解决了基于用户的协同过滤算法存在的性能瓶 颈。

     

    3.基于关联规则推荐

         基于关联规则的推荐(Association Rule-based Recommendation)是以关联规则为基础,把已购商品作为规则头,规则体为推荐对象。关联规则挖掘可以发现不同商品在销售过程中的相关性,在零售业中已经得到了成功的应用。管理规则就是在一个交易数据库中统计购买了商品集X的交易中有多大比例的交易同时购买了商品集Y,其直观的意义就是用户在购买某些商品的时候有多大倾向去购买另外一些商品。比如购买牛奶的同时很多人会同时购买面包。

    算法的第一步关联规则的发现最为关键且最耗时,是算法的瓶颈,但可以离线进行。其次,商品名称的同义性问题也是关联规则的一个难点。

     

    4.基于效用推荐

        基于效用的推荐(Utility-based Recommendation)是建立在对用户使用项目的效用情况上计算的,其核心问题是怎么样为每一个用户去创建一个效用函数,因此,用户资料模型很大程度上是由系统所采用的效用函数决定的。基于效用推荐的好处是它能把非产品的属性,如提供商的可靠性(Vendor Reliability)和产品的可得性(Product Availability)等考虑到效用计算中。

     

    5.基于知识的推荐

        基于知识的推荐(Knowledge-based Recommendation)在某种程度是可以看成是一种推理(Inference)技术,它不是建立在用户需要和偏好基础上推荐的。基于知识的方法因它们所用的功能知识不同而有明显区别。效用知识(Functional Knowledge)是一种关于一个项目如何满足某一特定用户的知识,因此能解释需要和推荐的关系,所以用户资料可以是任何能支持推理的知识结构,它可以是用户已经规范化的查询,也可以是一个更详细的用户需要的表示。

    6.组合推荐

       由于各种推荐方法都有优缺点,所以在实际中,组合推荐(Hybrid Recommendation)经常被采用。研究和应用最多的是内容推荐和协同过滤推荐的组合。最简单的做法就是分别用基于内容的方法和协同过滤推荐方法去产生一个推荐预测结果,然后用某方法组合其结果。尽管从理论上有很多种推荐组合方法,但在某一具体问题中并不见得都有效,组合推荐一个最重要原则就是通过组合后要能避免或弥补各自推荐技术的弱点。

    在组合方式上,有研究人员提出了七种组合思路:
       1)加权(Weight):加权多种推荐技术结果。
    2)变换(Switch):根据问题背景和实际情况或要求决定变换采用不同的推荐技术。
    3)混合(Mixed):同时采用多种推荐技术给出多种推荐结果为用户提供参考。
    4)特征组合(Feature combination):组合来自不同推荐数据源的特征被另一种推荐算法所采用。
    5)层叠(Cascade):先用一种推荐技术产生一种粗糙的推荐结果,第二种推荐技术在此推荐结果的基础上进一步作出更精确的推荐。
    6)特征扩充(Feature augmentation):一种技术产生附加的特征信息嵌入到另一种推荐技术的特征输入中。
    7)元级别(Meta-level):用一种推荐方法产生的模型作为另一种推荐方法的输入。

     

    主要推荐方法的对比

    各种推荐方法都有其各自的优点和缺点,见表1。

    表1 主要推荐方法对比

    推荐方法 优点 缺点
    基于内容推荐        推荐结果直观,容易解释;                 

     

    不需要领域知识

    新用户问题;                         

     

    复杂属性不好处理;

    要有足够数据构造分类器

    协同过滤推荐 新异兴趣发现、不需要领域知识;

     

    随着时间推移性能提高;

    推荐个性化、自动化程度高;

    能处理复杂的非结构化对象

    稀疏问题;

     

    可扩展性问题;

    新用户问题;

    质量取决于历史数据集;

    系统开始时推荐质量差;

    基于规则推荐 能发现新兴趣点;

     

    不要领域知识

    规则抽取难、耗时;

     

    产品名同义性问题;

    个性化程度低;

    基于效用推荐 无冷开始和稀疏问题;

     

    对用户偏好变化敏感;

    能考虑非产品特性

    用户必须输入效用函数;

     

    推荐是静态的,灵活性差;

    属性重叠问题;

    基于知识推荐 能把用户需求映射到产品上;

     

    能考虑非产品属性

    知识难获得;

     

    推荐是静态的

    展开全文
  • 基于协同过滤算法内容推荐算法实现电影推荐系统 本电影推荐系统算法是基于人人相似的协同过滤算法和基于内容的推荐算法相结合的混合推荐算法 混合推荐算法大致流程: 首先对数据集使用人人相似的协同过滤算法, 计算...
  • 基于内容的推荐算法

    万次阅读 2017-11-16 22:44:58
    但是,工业界真正使用的系统一般都不会只有CF推荐算法,Content-based Recommendations (CB) 基本也会是其中的一部分。CB应该算是最早被使用的推荐方法吧,它根据用户过去喜欢的产品(本文统称为 item),为用户推荐
  • 基于内容的推荐只考虑了对象本身性质,将对象按照标签形成集合,如果你消费集合中的一个则向你推荐集合中其他的对象;根据物品或内容的元数据,发现物品或内容的相关性,然后基于用户以前的的喜好记录推送给用户相似...
  • 基于内容的推荐算法基于内容推荐的步骤 对数据内容分析,得到物品的结构化描述 分析用户过去的评分或评论过的物品的,作为用户的训练样本 生成用户画像 a.可以是统计的结果(后面使用相似度计算) b.也可以是一个...
  • Dijkstra算法原理

    万次阅读 多人点赞 2017-02-19 22:46:13
    Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。 问题描述:在无向图 G=(V,E) 中,假...
  • 目前推荐系统研宄的主要趋势是从单一的、独立的推荐系统算法逐渐向组合多种推荐算法形成混合式的综合推荐算法方向发展,越来越多的结合用户标签数据、社交网络数据、上下文信息、地理位置信息。群体推荐也成为一个...
  • 遗传算法

    万次阅读 多人点赞 2019-04-06 21:41:47
    全部内容如下: 1、问题描述 编程实现遗传算法,并求解多峰函数的最大值。多峰函数的表达式如下所示: 用MATLAB做出函数的图像如下: 2、算法描述及实现 2.1、遗传算法概述 遗传算法(GA,Genetic Algorithm),也...
  • 音频算法工程师面试内容

    千次阅读 2020-02-29 16:26:21
    因为最近都参加了好几家公司的音频算法工程师面试主要总结一下 1.自我介绍 2.会根据你自我介绍的内容针对性的提问 3.讲一下AEC都有哪些步骤 4.讲一下自适应滤波的原理 5.NLP的步骤 6.噪声估计的方法有几种 ...
  • 新闻内容去重算法simhash实践

    千次阅读 2017-02-16 18:50:18
    前言  最近做了新闻去重算法的工作,mark下  两个应用场景:1. 重复新闻整体检测、去重 2. 从非重复的新闻中寻找重复的句子,依次判断两篇新闻... 我提供内容的检测算法 一 通用网页去重算法框架   二 simhash
  • 基于内容的推荐算法CB

    千次阅读 2015-09-20 15:03:13
    但是,工业界真正使用的系统一般都不会只有CF推荐算法,Content-based Recommendations (CB) 基本也会是其中的一部分。  CB应该算是最早被使用的推荐方法吧,它根据用户过去喜欢的产品(本文统称为
  • 本章主要谈谈基于内容Content Based推荐算法 CB推荐算法主要有两种子推荐算法: 1、引入item属性的Content Based推荐 2、引入user属性的Content Based推荐 先讲一下item内容属性索引构建: 1、对item的元信息...
  • 算法分析与设计|主要内容整理

    千次阅读 多人点赞 2020-06-16 19:51:46
    今天算法课程的考试结束了,对这一周以来的复习内容进行下整理~ 相对本科的算法学习,老师让我们从今日份考试中感受到算法分析与设计的重要,而不只是再停留在会做做题的阶段。 上一周的复习很充实,看算法与看...
  • 网站内容热点排序算法

    千次阅读 2018-05-29 22:47:44
    通用排序 单位时间内的交互数, 总交互数,总点赞数 评论数加权 按时间排序 可以利用redis来做,利用sortedSet(优先队列)来存储,后台开启一个线程一直来做这件事。...Score = (P - 1) \div...
  • 算法讲座,算法公开课,创业活动,算法班集锦 近期活动: 2014年9月3日,第8次西安面试&算法讲座视频 + PPT 的下载地址:http://blog.csdn.net/v_july_v/article/details/7237351#t40; 2014年10月18日,...
  • 主流推荐算法

    千次阅读 2018-11-13 17:11:22
    主流推荐算法大致可分为:  基于内容(相似度)的推荐  基于用户(User)/物品(Item)相似度的协同过滤  热点新闻推荐(你看到的那些头条新闻) ...1、内容算法推荐之爆款 2、四种推荐算法摘录 融...
  • 全面揭秘快手与抖音的内容推荐算法

    万次阅读 多人点赞 2019-04-17 22:02:48
    快抖的视频内容分为推荐(发现)、附近(同城)和关注三个模块,这里主要说明推荐模块的算法机制。 视频与用户画像的匹配程度 热度(赞、评论、转发等) 发布时间 根据用户数据和内容标签计算两者的匹配程度,是...
  • 网页正文及内容提取算法

    千次阅读 2016-05-23 14:18:09
    基于行块分布函数的通用网页正文抽取 ... 网页正文及内容图片提取算法 http://www.jianshu.co
  • SHA256算法原理详解

    万次阅读 多人点赞 2018-07-03 23:07:30
    SHA-2,名称来自于安全散列算法2(英语:Secure Hash Algorithm 2)的缩写,一种密码散列函数算法标准,由美国国家安全局研发,属于SHA算法之一,是SHA-1的后继者。 SHA-2下又可再分为六个不同的算法标准 包括了:...
  • 排序算法系列:快速排序算法

    万次阅读 多人点赞 2016-03-01 15:40:07
     在前面说到了两个关于交换排序的算法:冒泡排序与奇偶排序。  本文就来说说交换排序的最后一拍:快速排序算法。之所以说它是快速的原因,不是因为它比其他的排序算法都要快。而是从实践中证明了快速排序在平均...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,149,957
精华内容 459,982
关键字:

内容算法