我试图计算出我编写的函数的时间复杂度(它生成一个电源组 http://en.wikipedia.org/wiki/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. 是否有更快的方法来生成幂集,或者这是否是最佳方法?
一条评论:
上面的函数是面试问题的一部分,程序应该接受一个字符串,然后打印出字典中的单词,这些单词的字母是输入字符串的字谜子集(例如输入:tabrcoz 输出:boat, car, cat , ETC。)。面试官声称 n*m 实现很简单(其中 n 是字符串的长度,m 是字典中的单词数),但我认为您无法找到给定字符串的有效子字符串。看来面试官的说法是错误的。
1995 年我在微软面试时也遇到了同样的面试问题。基本上问题是实现一个简单的拼字游戏播放算法。
你用这种产生动力组的想法完全错了。不错的想法,显然太贵了。放弃它并寻找正确的答案。
这是一个提示:对字典进行分析,构建一个新的数据结构,更适合有效地解决您实际需要解决的问题。通过优化的字典,您应该能够实现 O(nm)。通过更巧妙构建的数据结构,您可能可以做得更好。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)