文字列のべき集合 (つまり、その文字列のすべての可能な部分列) の計算に動的計画法を使用して、計算数を大幅に削減することは可能ですか?
1496 次
2 に答える
2
いいえ。累乗集合を計算している場合は、常に同じ数の要素を持つ累乗集合を計算しています。
于 2012-05-02T13:03:20.860 に答える
2
何らかの方法で各出力ビットを通過する必要があるため、出力のサイズに比例して複雑さを減らすことはできません。これは、使用するアルゴリズムに関係なく、すべての問題に当てはまります。したがって、2^n はべき乗集合の計算の下限です。これは、2^n 個の文字列を出力する必要があるためです (すべての文字列は複数の文字であり、平均して n に依存するため、さらに高くなります)。
于 2012-05-02T14:03:27.680 に答える