幂集生成函数的时间复杂度 [英] Time complexity of a powerset generating function

问题描述

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

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:

• 让输入字符串的大小为n
• 在外部 for 循环中，必须迭代 2^n 次(因为设置的大小是 2^n).
• 在内部 for 循环中，我们必须迭代 2*n 次(最坏的情况).

1.所以 Big-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 输出:船，汽车、猫等).面试官声称 n*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.

这篇关于幂集生成函数的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！