performance - 指定されたサイズのすべてのサブセットを反復する

Question

サイズ n のセットのすべてのサブセットを反復することはパフォーマンスの悪夢であり、O(2^n) 時間かかることを私は知っています。

サイズ k ((0 <= k <= n) の場合) のすべてのサブセットを反復処理するのはどうですか? それはパフォーマンスの悪夢ですか？(n, k) = n があることは知っています。/k！(n-k)! 可能性。k が 0 に非常に近い場合、または n に非常に近い場合、これは小さい数です。

n と k に関する最悪の場合のパフォーマンスは? O(n! / k! (n - k)!) 以外の簡単な言い方はありますか? これは漸近的に O(n!) よりも小さいですか、それとも同じですか?

Answer 1

nが固定されている場合、(n, k)が で最大になることを示すのは簡単k = n/2です。スターリングの近似を誤って適用していなければ、 の漸近挙動(n, n/2)は指数関数的です。

定数kの場合(n, k)は ですO(n^k)。組み合わせ関数は対称であるため、 についても同じであることに注意して(n, n-k)ください。これは多項式なので、 よりもはるかに小さいですO(n!)。