两种算法的Big-O分析

Question

我为 leetcode problem 17 创建了两个解决方案，其中要求您从 phone 数字组合生成所有可能的文本字符串，例如"3" 结果为 ["d","e","f"]。

我的第一个解决方案使用递归算法生成字符串，如下所示：

class Solution {
public:
    void fill_LUT(vector<string>& lut) {
        lut.clear();
        lut.push_back(" ");
        lut.push_back("");
        lut.push_back("abc");
        lut.push_back("def");
        lut.push_back("ghi");
        lut.push_back("jkl");
        lut.push_back("mno");
        lut.push_back("pqrs");
        lut.push_back("tuv");
        lut.push_back("wxyz");
    }

    void generate_strings(int index, string& digits, vector<string>& lut, vector<string>& r, string& work) {
        if(index >= digits.size()) {
            r.push_back(work);
            return;
        }

        char idx = digits[index] - '0';
        for(char c : lut[idx]) {
            work.push_back(c);
            generate_strings(index+1, digits, lut, r, work);
            work.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        vector<string> r;
        vector<string> lut;
        fill_LUT(lut);

        if(digits.size() <= 0)
            return r;

        string work;
        generate_strings(0, digits, lut, r, work);

        return r;
    }
};

我对 big-O 有点生疏，但在我看来，space 复杂度对于递归调用来说是 O(n)，即它的最大深度，O(n)对于缓冲区字符串，O(n*c^n) 对于结果字符串。总和为 O(n+n*c^n)?

对于时间复杂度，我有点困惑。递归的每一层执行c pushes + pops + 递归调用乘以下一层的操作数，所以听起来像c^1 + c^2 + ... + c^n。此外，还有 c^n 个重复 n 长度的字符串。 如何将其合并为一个漂亮的大 O 表示？

第二种解决方案将结果数视为混合基数并将其转换为字符串，就像您可能执行 int 到 hex 字符串转换一样：

class Solution {
public:
    void fill_LUT(vector<string>& lut) {
        lut.clear();
        lut.push_back(" ");
        lut.push_back("");
        lut.push_back("abc");
        lut.push_back("def");
        lut.push_back("ghi");
        lut.push_back("jkl");
        lut.push_back("mno");
        lut.push_back("pqrs");
        lut.push_back("tuv");
        lut.push_back("wxyz");
    }

    vector<string> letterCombinations(string digits) {
        vector<string> r;
        vector<string> lut;
        fill_LUT(lut);

        if(digits.size() <= 0)
            return r;

        unsigned total = 1;
        for(int i = 0; i < digits.size(); i++) {
            digits[i] = digits[i]-'0';
            auto m = lut[digits[i]].size();
            if(m > 0) total *= m;
        }

        for(int i = 0; i < total; i++) {
            int current = i;
            r.push_back(string());
            string& s = r.back();
            for(char c : digits) {
                int radix = lut[c].size();
                if(radix != 0) {
                    s.push_back(lut[c][current % radix]);
                    current = current / radix;
                }
            }
        }

        return r;
    }
};

在这种情况下，我认为 space 复杂度是 O(n*c^n) 类似于第一个解决方案减去缓冲区和递归，并且时间复杂度必须是 O(n) 对于第一个for 循环和一个额外的 O(n*c^n) 来为每个可能的结果创建一个结果字符串。最后的大 O 是 O(n+n*c^n)。 我的思维过程是否正确？

编辑： 为了对代码进行一些说明，想象一下 "234" 的输入字符串。第一个递归解决方案将使用参数 (0, "234", lut, r, work) 调用 generate_strings。 lut 是一个查找 table ，它将数字转换为其对应的字符。 r 是包含结果字符串的向量。 work 是执行工作的缓冲区。

然后第一个递归调用将看到索引 0 数字是 2 对应于 "abc"，将 a 推到 work，并且然后使用参数 (1, "234", lut, r, work) 调用 generate_strings。一旦调用 returns，它就会将 b 推到 work 并冲洗并重复。

当 index 等于 digits 的大小时，将生成一个唯一的字符串并将该字符串推入 r.

对于第二种解决方案，首先将输入字符串从它的 ascii 表示形式转换为它的整数表示形式。例如 "234" 转换为 "\x02\x03\x04"。然后代码使用这些作为索引来查找查找中相应字符的数量 table 并计算结果中的字符串总数。例如如果输入字符串是 "234"，2 对应 abc，它有 3 个字符。 3 对应有 3 个字符的 def。 4 对应有 3 个字符的 ghi。可能的字符串总数为 3*3*3 = 27。

然后代码使用一个计数器来表示每个可能的字符串。如果 i 是 15，它将通过首先找到 15 % 3 进行评估，即 0，对应于第一个数字的第一个字符 (a)。然后用 15 除以 3 即 5。 5 % 3 是 2 对应第二个数字的第三个字符，即 f。最后用 5 除以 3 得到 1。 1 % 3 是 1 对应第三个数字的第二个字符 h。因此与数字 15 对应的字符串是 afh。对每个数字执行此操作，结果字符串存储在 r.

中

Answer 1

递归算法：

Space：每一层递归都是O(1)，还有O(n)层。因此，递归是 O(n)。结果的 space 是 O(c^n)，其中 c = max(lut[i].length)。该算法的总 space 为 O(c^n)。

时间：令 T(n) 为长度为 n 的数字的成本。然后我们有递归公式：T(n) <= c T(n-1) + O(1)。求解这个等式给出 T(n) = O(c^n).

哈希算法：

Space：如果需要space来存储所有的结果，那么还是O(c^n).

时间：O(n+c^n) = O(c^n)。

我喜欢散列算法，因为如果问题要求您给出特定的字符串结果（假设我们按字母顺序排列它们）会更好。在那种情况下，space 和时间仅为 O(n)。

这个问题让我想起了一个类似的问题：生成集合{1,2,3,...,n}的所有排列。哈希方法更好，因为通过一个一个地生成排列并对其进行处理，我们可以节省很多 space.

两种算法的Big-O分析

Big-O analysis of two algorithms

c++

algorithm

recursion

big-o