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

Question

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

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

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

score 4 · Accepted Answer

是的，使用哈希就可以了O(NM)。在这种情况下，该过程称为记忆化（是的，没有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)，但您可以使用其他数学方法获得更紧密的界限。

1 回答 1