时间幂生成函数

我想弄清楚，我写了一个函数的时间复杂度的复杂性（它给定的字符串生成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
，必须重复2^n倍（因为集合大小是2^N）。
在内循环中，我们必须迭代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.是否有更快的方式来产生功率集，或者这是否最优？

来源

2011-01-07 Kiril

我实际上并不知道c＃，但我相信string.concat必须复制每个调用的字符串，这意味着复杂度实际上是O（n^2 * 2^n）。 – 2011-01-08 11:14:41

@Chris，感谢您的参与。 – Kiril 2011-01-08 23:17:25

注释：

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

1995年我在微软采访时，我被给了同样的面试问题。基本上问题是实现一个简单的Scrabble播放算法。

你正在用完全产生功率集的想法完全错误地发出树。尼斯认为，显然太昂贵了。放弃它，找到正确的答案。

这里有一个提示：在字典上运行分析，建立一个新的数据结构，更有效地解决你实际上必须解决的问题。使用优化字典，您应该能够实现O（nm）。有了更巧妙的数据结构，你甚至可以做得更好。

来源

2011-01-08 05:39:08

2.有没有更快的方法来产生一个功率集，或者这是最佳的？

你的算法是合理的，但你的字符串处理可以使用改进。

string str = Convert.ToString(i, 2); 
string pset = str; 
for (int k = str.Length; k < input.Length; k++) 
{ 
    pset = "0" + pset; 
}

所有你在这里做的是设置一个位域，但使用一个字符串。只需跳过此操作，并直接使用变量i。

for (int j = 0; j < input.Length; j++) 
{ 
    if (i & (1 << j)) 
    {

当您构建字符串时，请使用StringBuilder，而不是创建多个字符串。

// At the beginning of the method 
StringBuilder set = new StringBuilder(input.Length); 
... 
// Inside the loop 
set.Clear(); 
... 
set.Append(input[j]); 
... 
powerSet.Add(set.ToString());

这是否会影响算法的复杂性？但是，它会显着减少您创建的额外String对象的数量，这将为您提供很好的加速。

来源

2011-01-07 22:19:07

你让我意识到，我可以只是做set = set + input [j] .ToString（），不会像使用StringBuilder一样快吗？ – Kiril 2011-01-07 22:27:34

时间幂生成函数

回答

相关问题