我试图计算出我编写的函数的时间复杂度(它为给定字符串生成 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。是否有更快的方法来生成幂集,或者这是否是最佳方法?
最佳答案
评论:
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 年我在微软面试时也遇到了同样的面试问题。基本上问题是实现一个简单的拼字游戏播放算法。
你用生成幂集的想法完全搞错了树。不错的想法,显然太贵了。放弃它并寻找正确的答案。
这里有一个提示:对字典进行分析,构建一个新的数据结构,更适合有效地解决您实际需要解决的问题。通过优化的字典,您应该能够实现 O(nm)。通过更巧妙构建的数据结构,您可能可以做得更好。
关于c# - 幂集生成函数的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4630670/