c++ - 两种算法的大O分析

Question

我为 leetcode problem 17 创建了两个解决方案它要求您从电话号码组合中生成所有可能的文本字符串，例如"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 有点生疏，但在我看来空间复杂度应该是 O(n)对于递归调用，即其最大深度， O(n)对于缓冲区字符串，和 O(n*c^n)对于结果字符串。将这个总和作为 O(n+n*c^n) ?

对于时间复杂度，我有点困惑。每一级递归执行 c pushes + pops + recursive call 乘以下一级的操作数，所以听起来像 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;
    }
};

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

编辑:为了给代码添加一些说明，想象一个输入字符串 "234" .第一个递归解决方案将调用 generate_strings带参数 (0, "234", lut, r, work) . lut是一个将数字转换为其相应字符的查找表。 r是包含结果字符串的 vector 。 work是执行工作的缓冲区。

第一次递归调用将看到索引 0数字是 2对应于 "abc" ，推 a至 work ，然后调用 generate_strings带参数 (1, "234", lut, r, work) .一旦调用返回，它将推送 b至 work并冲洗并重复。

当 index等于 digits的大小然后生成了一个唯一的字符串并将该字符串推送到 r .

对于第二种解决方案，输入字符串首先从它的 ascii 表示转换为它的整数表示。例如 "234"转换为 "\x02\x03\x04" .然后代码使用这些作为索引在查找表中查找相应字符的数量，并计算结果中的字符串总数。例如如果输入字符串是 "234" , 2对应 abc , 有 3 个字符。 3对应 def其中有 3 个字符。 4对应 ghi其中有 3 个字符。可能的字符串总数为 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

递归算法:

空间:每一级递归都是 O(1) 并且有 O(n) 级。因此，递归是 O(n)。结果的空间是 O(c^n)，其中 c = max(lut[i].length)。算法的总空间为 O(c^n)。

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

哈希算法:

空间:如果你需要空间来存储所有结果，那么它仍然是 O(c^n)。

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

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

这个问题让我想起了一个类似的问题:生成集合 {1,2,3,...,n} 的所有排列。散列方法更好，因为通过逐一生成排列并对其进行处理，我们可以节省大量空间。