两种算法的Big-O分析

Question

我为leetcode问题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推送+弹出+递归调用乘以下一级别的操作数,所以听起来像c^1 + c^2 + ... + c^n.此外,还有长度字符串的c^n重复n.如何将其合并为一个漂亮的大O表示？

---

第二个解决方案将结果数视为混合基数,并将其转换为字符串,因为您可能执行int到十六进制字符串转换:

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是包含结果字符串的向量.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}的所有排列。散列方法更好，因为通过一一生成排列并对其进行处理，我们可以节省大量空间。