コード日進月歩

しんくうの技術的な小話、メモ、つれづれ、など

組み合わせ爆発についてざっくりまとめる

日本語特有の表現かと思ったらそうではなかったのでメモ

意味

問題を解く過程にある、内容のかけ合わせが増大する事例のことをいう。

組み合わせのかけ合わせが増えれば増えるほどパターンが増えるという事例は下記を見ていただくとわかりやすい。

『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう! - YouTube

語られ始めた時期

英語版のWikipedaで初めて記事が作られたのが2006年、その前年の2005年にも "combinatorial explosion" の記載がある論文がちらほらあるので、その頃から出てきた言葉かと思われる。

関連するフレーズ

指数関数的に増える(指数関数的増加)

指数関数は線形的な関数に比べて、数の上がり方が急激に増えるため、その性質になぞらえて指数関数的〜という表現がされる。

こちらに関しても下記サイトで図が紹介されているので参照のこと。

増え方に着目してみよう ~ねずみ算と指数関数~

参考リンク