我看看子快于O（N * N） [英] Can i check if subsequence faster then O(n*n)

问题描述

所以我的问题是主题的名称。是否存在一种算法来检查，如果B是的快子，比O（N ^ 2），例如O（NlogN）或者干脆O（N）？

唯一的办法找到简单香槟力

 的for（int i = 0; I＆LT;则为a.length  -  b.length个;我++）
{
   如果（IsSubsequence（A，B，i））的
      返回我;
}
返回-1;
 

解决方案

下面的大卫Eisenstat算法的递归特性。 （请注意，此算法的尾递归的，因此可以被写为一个循环，我把它描述为递归的，因为这样做是一个很好的方式来理解算法）

定义一个序列作为空，或者在一个序列的项目。

取两个序列，A和B的问题是，如果B是或不是的序列。

如果B为空，那么B是A的子序列。

如果B不是空的，一个是空的那么B不是A的一个子序列。

如果我们做了这么远，A和B都不是空的。假设A是X项后面序列C，B是项Ÿ其次是序列D。

如果X是与当前Y则问题的答案是乙A的一个子序列？是一样的答案的问题较小的D C的子序列？。回答这个问题。

如果X不是与当前Y则问题的答案是乙A的一个子序列？是一样的答案与较小的问题是B C的子序列？。回答这个问题。

这个过程终止，并明确其最坏的情况是在序列A的长度。

So my question is in topic's name. Does exists an algorithm that checks if B is subsequence of A faster, than O(N^2), for example O(NlogN) or simply O(N)?

Only way found is simple brut-force

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

解决方案

Here's a recursive characterization of David Eisenstat's algorithm. (Note that this algorithm is tail recursive and can therefore be written as a loop; I describe it as recursive because doing so is a nice way to understand the algorithm.)

Define a sequence as either empty, or an item followed by a sequence.

Take two sequences, A and B. The question is if B is or is not a subsequence of A.

If B is empty then B is a subsequence of A.

If B is not empty and A is empty then B is not a subsequence of A.

If we've made it this far, neither A nor B are empty. Suppose that A is item X followed by sequence C and B is item Y followed by sequence D.

If X is the same as Y then the answer to the question "is B a subsequence of A?" is the same as the answer to the smaller question "is D a subsequence of C?". Answer that question.

If X is not the same as Y then the answer to the question "is B a subsequence of A?" is the same as the answer to the smaller question "is B a subsequence of C?". Answer that question.

This procedure terminates and clearly its worst case is in the length of the sequence A.

这篇关于我看看子快于O（N * N）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！