为了正确理解它,请仔细查看图表,并在阅读图表时按照递归自上而下的方法进行。
Here, xstr = "ABCD"
ystr = "BAEC"
lcs("ABCD", "BAEC") // Here x != y
/ \
lcs("BCD", "BAEC") <-- x==y --> lcs("ABCD", "AEC") x==y
| |
| |
lcs("CD", "AEC") <-- x!=y --> lcs("BCD", "EC")
/ \ / \
/ \ / \
/ \ / \
lcs("D","AEC") lcs("CD", "EC") lcs("BCD", "C")
/ \ / \ / \
lcs("", "AEC") lcs("D","EC") lcs("CD", "C") lcs("BCD","")
| \ / \ | / |
Return lcs("", "EC") lcs("D" ,"C") lcs("D", "") lcs("CD","") Return
/ \ / \ / \ / \
Return lcs("","C") lcs("D","") lcs("","") Return lcs("D","") Return
/ \ / \ / / \
Return lcs("","") Return lcs("", "") Return
| |
Return Return
注意:通常使用树形结构来表示递归调用的正确方式,但在这里我使用了图形方法来压缩树形结构,以便读者可以轻松理解递归调用。当然,这也更容易让我进行表达。
由于上图中有一些冗余对,例如lcs("CD", "EC")
是从lcs("CD", "AEC")
中删除"A"
和"BCD"
是从lcs("BCD", "EC")
中删除"B"
得到的结果。因此,在执行过程中会多次调用这些对,这增加了程序的时间复杂度。
正如您可以轻松看出每个对都会生成两个结果,直到遇到任何空字符串或x==y
为止。因此,如果字符串的长度分别为n,m (考虑xstr的长度为n
,ystr的长度为m
,我们考虑最坏情况)。那么,最终我们将有2n+m个结果。(如何思考?)
既然n+m是一个整数,假设为N。因此,算法的时间复杂度为:O(2N),对于较大的N值来说并不高效。
因此,我们更喜欢使用动态规划方法而不是递归方法。它可以将时间复杂度降低到:O(n.m) => O(n2),当n == m时。
即使现在您还很难理解逻辑,我建议您为xstr="ABC"
和ystr="EF"
制作一个树形结构
表示(不是我展示的图形)。我希望您能理解它。
如有疑问,请随时发表评论。