c# – 我可以检查子序列是否比O(n * n)更快

发布时间：2020-12-16 00:10:54 所属栏目：百科来源：网络整理

导读：所以我的问题是主题的名称.是否存在一种算法,该算法检查B是否是A的子序列,比O(N ^ 2)更快,例如O(NlogN)或简单地O(N)？找到的方法就是简单的残酷力量 for(int i = 0; i a.Length - b.Length; i++){ if (IsSubsequence(a,b,i)) return i;}return -1; 解决方法

所以我的问题是主题的名称.是否存在一种算法,该算法检查B是否是A的子序列,比O(N ^ 2)更快,例如O(NlogN)或简单地O(N)？

找到的方法就是简单的残酷力量

for(int i = 0; i < a.Length - b.Length; i++)
{
   if (IsSubsequence(a,b,i))
      return i;
}
return -1;

解决方法

这是David Eisenstat算法的递归表征. (请注意,此算法是尾递归的,因此可以写为循环;我将其描述为递归,因为这样做是理解算法的好方法.)

将序列定义为空,或将项目定义为序列.

取两个序列,A和B.问题是B是否是A的子序列.

如果B为空,那么B是A的子序列.

如果B不为空且A为空,则B不是A的子序列.

如果我们做到这一点,A和B都不是空的.假设A是项目X,后面是序列C,B是项目Y,后面是序列D.

如果X与Y相同,那么问题的答案是“B是A的子序列？”与小问题的答案相同“是D是C的子序列吗？”.回答那个问题.

如果X与Y不同,那么问题的答案是“B是A的子序列？”与小问题的答案相同“是B是C的子序列吗？”.回答那个问题.

这个过程终止,显然最坏的情况是序列A的长度.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!