c# - 幂集生成函数的时间复杂度

Question

我正在尝试计算我编写的函数的时间复杂度(它为给定字符串生成 power set):

public static HashSet<string> GeneratePowerSet(string input)
{
    HashSet<string> powerSet = new HashSet<string>();

    if (string.IsNullOrEmpty(input))
        return powerSet;

    int powSetSize = (int)Math.Pow(2.0, (double)input.Length);

    // Start at 1 to skip the empty string case
    for (int i = 1; i < powSetSize; i++)
    {
        string str = Convert.ToString(i, 2);
        string pset = str;
        for (int k = str.Length; k < input.Length; k++)
        {
            pset = "0" + pset;
        }

        string set = string.Empty;
        for (int j = 0; j < pset.Length; j++)
        {
            if (pset[j] == '1')
            {
                set = string.Concat(set, input[j].ToString());
            }
        }
        powerSet.Add(set);
    }
    return powerSet;
}

所以我的尝试是这样的:

• 令输入字符串的大小为n
• 在外层for循环中，必须迭代2^n次(因为集合大小为2^n)。
• 在内部 for 循环中，我们必须迭代 2*n 次(最坏情况下)。

<强>1。所以 Big-O 将是 O((2^n)*n)(因为我们去掉了常量 2)...对吗？

而且 n*(2^n) 比 n^2 差。

如果 n = 4 那么
(4*(2^4)) = 64
(4^2) = 16

如果 n = 100 那么
(10*(2^10)) = 10240
(10^2) = 100

<强>2。是否有更快的生成幂集的方法，或者这是否是最优的？

Answer 1

一条评论:

the above function is part of an interview question where the program is supposed to take in a string, then print out the words in the dictionary whose letters are an anagram subset of the input string (e.g. Input: tabrcoz Output: boat, car, cat, etc.). The interviewer claims that a n*m implementation is trivial (where n is the length of the string and m is the number of words in the dictionary), but I don't think you can find valid sub-strings of a given string. It seems that the interviewer is incorrect.

我 1995 年在 Microsoft 面试时被问到同样的面试问题。基本上问题是实现一个简单的拼字游戏播放算法。

您完全错误地提出了生成幂集的想法。不错的想法，显然太贵了。放弃它并找到正确的答案。

这里有一个提示:对字典进行分析，构建一个新的数据结构，更适合有效地解决您实际必须解决的问题。使用优化的字典，您应该能够实现 O(nm)。使用更巧妙构建的数据结构，您可能会做得更好。