我想弄清楚，我写了一个函数的时间复杂度（它生成一个发电机组获取给定的字符串）：

I'm trying to figure out the time complexity of a function that I wrote (it generates a power set for a given string):

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;
}

所以，我的尝试是这样的：

So my attempt is this:

1。因此，大O是O（（2 ^ N）* N）（因为我们放弃了常数2）...是正确的？

和n *（2 ^ n）是大于n差^ 2。

And n*(2^n) is worse than n^2.

如果n = 4，则 （4 *（2 ^ 4））= 64 （4 ^ 2）= 16

if n = 4 then (4*(2^4)) = 64 (4^2) = 16

如果n = 100，然后 （10 *（2 ^ 10））= 10240 （10 ^ 2）= 100

if n = 100 then (10*(2^10)) = 10240 (10^2) = 100

2。有没有更快的方法来产生功率设定，或者这是关于最优？

推荐答案

注释：

以上功能的面试问题，其中的程序应该采取一个字符串，然后打印出在字典中的字母输入字符串的字谜子集的话部分（例如输入：tabrcoz输出：船，车，猫等）。采访者声称，一个* m的实现很简单（其中n是字符串的长度，m是词在字典中的数量），但我不认为你可以找到有效的子串给定字符串。看来，面试官是不正确。

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年接受采访回来基本上，问题是要实现一个简单的拼字游戏打算法。

I was given the same interview question when I interviewed at Microsoft back in 1995. Basically the problem is to implement a simple Scrabble playing algorithm.

正在狂吠起来完全错了这个想法产生的电力集。很好的想法，显然太昂贵。放弃它，并找到正确的答案。

You are barking up completely the wrong tree with this idea of generating the power set. Nice thought, clearly way too expensive. Abandon it and find the right answer.

下面有一个提示：运行分析越过那建立一个新的数据结构更适合于有效地解决这个问题，你真正要解决的字典。通过优化的字典，你应该能够达到O（NM）。随着更巧妙的内置数据结构，你也许可以做到，甚至比这更好的。

Here's a hint: run an analysis pass over the dictionary that builds a new data structure more amenable to efficiently solving the problem you actually have to solve. With an optimized dictionary you should be able to achieve O(nm). With a more cleverly built data structure you can probably do even better than that.