algorithm - 记忆化在最长公共(public)子序列递归求解中的优势

Question

我在 geekforgeeks 阅读了一篇关于解决 Longest Common Subsequence 问题的文章，其中有两种解决方案，一种是递归的，另一种是通过二维数组的 DP。 DP 解决方案在 O(NM) 时间内完成，而递归解决方案在 O(2^N) 时间内完成。

递归解决方案的主要问题是子序列重叠的发生，正如那里给出的那样。但是，如果我将每一对存储在散列中，那么下次函数递归需要该值时，它可以直接从散列中获取值，而不是进一步递归。那么这个加法会提高多少效率呢？它会到达 O(NM) 吗？

其次，递归解决方案如何产生 O(2^N) 时间？如何找出像这样的递归函数的复杂性，或者找到斐波那契数列的递归函数等？

Answer 1

是的，使用散列会使它成为 O(NM)。在这种情况下，该过程称为 memoization (是的，没有 r)。只要确保你不使用你选择的语言提供的实际 hashmap 容器，让它成为一个简单的矩阵:如果当前对的值是 -1，递归计算它，否则假设它已经被计算并返回它。

至于你的第二个问题，你可以通过数学方式来获得最佳界限，或者像你的链接那样在纸上画出来“足够好”:

                f(n)
               /    \
         f(n-1)      f(n-2)
        /     \        
  f(n-2)       f(n-3)
          ...

这应该足以归纳地表明它将是 O(2^n):树的高度为 n，并且在每个节点处，您有两个递归将问题从大小 n 减少到大小 n - 1 的调用(这将是 O(2^(n - 1))。所以大小 n 原始问题将是 O(2^n)。

请注意，斐波那契数列为 O(2^n) 并没有错，但您可以通过其他数学方法获得更紧密的约束。