0

是否可以在计算字符串的幂集(即该字符串的所有可能子序列)时使用动态规划来显着减少计算次数?

4

2 回答 2

2

不。如果您正在计算一个幂集,那么您正在计算一个幂集,它始终具有相同数量的元素。

于 2012-05-02T13:03:20.860 回答
2

您永远无法将复杂性降低到与输出大小成线性关系以下,因为您需要以某种方式遍历每个输出位。无论使用何种算法,所有问题都是如此。所以 2^n 是计算幂集的下限,因为你需要输出 2^n 个字符串(每个字符串都是多个字符,平均取决于 n,所以甚至更高)。

于 2012-05-02T14:03:27.680 回答