对于求取两个长度为n的字符串的最长公共子序列问题,利用(41)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。A.贪心B.分治C.分支-限界D.动态规划

题目

对于求取两个长度为n的字符串的最长公共子序列问题,利用(41)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。

A.贪心

B.分治

C.分支-限界

D.动态规划


相似考题
更多“对于求取两个长度为n的字符串的最长公共子序列问题,利用(41)策略可以有效地避免子串最长公共子序 ”相关问题
  • 第1题:

    求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为( )。经分析发现该问题具有最优子结构,可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j],如下式所示。



    采用自底向上的方法实现该算法,则时间复杂度为(请作答此空)

    A.O(n^2)
    B.O(n^21gn)
    C.O(n^3)
    D.O(n2^n)

    答案:A
    解析:
    蛮力法,对X的每一个子序列,判断是否也是Y的子序列,其中,长度为n的序列X共有2^n个子序列,判断其是否是Y的子序列时间是n,因此是n*2^n;采用动态规划法自底向上实现时,根据递归公式,实际是关于i和j的两重循环,因此时间复杂度是n^2.

  • 第2题:

    1、给定两个序列分别为“algorithm”和“glorhythm”。则以下分别为两序列的最长公共子序列和最长公共子串的选项是____

    A.gorthm thm

    B.thm gorthm

    C.glorhthm orthm

    D.orthm glorhthm


    gorthm thm

  • 第3题:

    如果仅需要求得最长公共子序列的代价,则最长公共子序列的空间复杂性可以降低到O(n),其中n是两个序列中任意一个的长度


    动态规划法

  • 第4题:

    求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(请作答此空)。经分析发现该问题具有最优子结构,可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j],如下式所示。



    采用自底向上的方法实现该算法,则时间复杂度为( )

    A.O(n^2)
    B.O(n^21gn)
    C.O(n^3)
    D.O(n2^n)

    答案:D
    解析:
    蛮力法,对X的每一个子序列,判断是否也是Y的子序列,其中,长度为n的序列X共有2^n个子序列,判断其是否是Y的子序列时间是n,因此是n*2^n;采用动态规划法自底向上实现时,根据递归公式,实际是关于i和j的两重循环,因此时间复杂度是n^2.

  • 第5题:

    给定两个序列分别为“algorithm”和“glorhythm”。则以下分别为两序列的最长公共子序列和最长公共子串的选项是____

    A.gorthm thm

    B.thm gorthm

    C.glorhthm orthm

    D.orthm glorhthm


    gorthm thm