説明変数の数が増えると計算量が指数関数的に増加するのはなぜ？

2024年6月25日

説明変数の数が増えると計算量が指数関数的に増加する理由は、組み合わせの数が急激に増えるためです。組み合わせの数は、説明変数の数に対して指数関数的に増加します。

説明変数が $n$n 個ある場合、それらの説明変数から異なる組み合わせを選ぶ方法の数は $2^n$2n です。つまり、各説明変数を含めるか含めないかの2通りがあり、それらの組み合わせが全て考慮されるためです。

たとえば、説明変数が5つある場合、異なる組み合わせの数は $2^5 = 32$25=32 となります。これは比較的まだ少ないですが、説明変数の数が増えるにつれて急速に増加します。たとえば、10個の説明変数がある場合、組み合わせの数は $2^{10} = 1024$210=1024 となります。20個の説明変数がある場合、組み合わせの数は $2^{20} = 1048576$220=1048576 となります。このように、説明変数の数が増えると、計算量は指数関数的に増加します。