使用映射的递归最长公共子序列的时间复杂度

Question

我正在阅读 Thomas H Corman 的 'Algorithms Unlocked'，并偶然发现了一种在 O(n * m) 中找到运行的最长公共子序列的方法。这种方法也可以在这篇文章中看到：https://www.geeksforgeeks.org/printing-longest-common-subsequence/

这似乎是最流行和最快的方法，但对我来说似乎有点令人费解，所以我尝试编写一种不同的方法，也使用动态编程。

我的方法是递归的，在最坏的情况下每次调用都必须 b运行ch 两次，但使用记忆来保存先前输入的结果。我知道 std::map 可以为 'find' 花费 lg(n) 时间，但我认为可以轻松更改此代码以使用哈希映射来代替

using namespace std;

string lcs_helper(int i, int j, const string& x, const string& y, map<pair<int, int>, string>& memoizedSolutions)
{
    if (memoizedSolutions.count({ i, j })) return memoizedSolutions[{i, j}]; 

    if (i == 0 || j == 0) return "";

    if (x[i] == y[j])
    {
        string lcs = lcs_helper(i - 1, j - 1, x, y, memoizedSolutions);
        lcs.push_back(x[i]);
        memoizedSolutions[{i, j}] = lcs;

        return lcs;
    }

    string lcs1 = lcs_helper(i - 1, j, x, y, memoizedSolutions);
    string lcs2 = lcs_helper(i, j - 1, x, y, memoizedSolutions);

    if (lcs1.size() >= lcs2.size()) // corrected bug
    {
        memoizedSolutions[{i, j}] = lcs1;
        return lcs1;
    }

    memoizedSolutions[{i, j}] = lcs2;
    return lcs2;
}

string lcs(string x, string y)
{
    map<pair<int, int>, string> memoizedSolutions;

    return lcs_helper(x.size() - 1, y.size() - 1, x, y, memoizedSolutions); 
}

我正在努力概括我的方法的时间复杂度，想知道它是否以及为什么比通常的方法慢。

我试图通过创建一个带有示例的树来理解时间复杂性，但仍在努力概括它。 https://imgur.com/a/h8J6ldH（这是我创建的树示例，红色= return ""，其他颜色代表可以记忆的输入，我省略了记忆结果的树）

Answer 1

即使使用hashmap进行memoization，修正bug，时间复杂度也是O(m*n*l)，其中l是LCS的长度；这也是 upper-bounded by O(m*n*min(m, n)).

首先，错误。 lcs_helper return 一个字符串：

string lcs1 = lcs_helper(i - 1, j, x, y, memoizedSolutions);
string lcs2 = lcs_helper(i, j - 1, x, y, memoizedSolutions);

if (lcs1 >= lcs2)

这个if语句应该比较字符串的长度；它实际上是按字典顺序比较它们。

要找到 dynamic-programming 算法的 time-complexity，一个方便的公式是 (number of subproblems) * (time to solve one subproblem)。
在这里，您有与常规 DP 解决方案相同数量的子问题：m*n，或者 i 和 j.

的每个值一个。

解决一个子问题的时间，在你的情况下，不是 O(1)。由于您的函数 return 是一个字符串，并且必须缓存字符串以进行记忆，因此每个子问题最多需要 length(LCS) 工作来构建字符串并复制内存。

这可能就是正常的 DP 算法看起来很复杂的原因：如果存储实际的 LCS 字符串，run-time 将在 worst-case 中变为立方体。通过仅记忆 LCS 的长度，并具有 lcs_helper return 长度，您需要在最后回溯以构建字符串，但保持 O(m*n) 运行时。

使用映射的递归最长公共子序列的时间复杂度

Time complexity of recursive Longest Common Subsequence which uses a map

algorithm

dynamic-programming

clrs

subsequence