首页 软考中级软件设计师正文

求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,

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

62.png

  A.  O(n²)
   B.  O(n²lgn)
   C.  O(n³)
   D.  O(n2)
 
  A.  O(n²)
   B.  O(n²lgn)
   C.  O(n³)
   D.  O(n2)







参考答案:D  A

参考解析:

版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,转载需标明出处。
如果您有更好的解答,欢迎留言评论。

本文链接:https://www.ruankaoti.com/post/875.html

评论

阅读更多

微信扫码,访问本站小程序

微信扫码进入小程序,获取更多软考资料

最近发表