計算量の爆発

デジタル大辞泉

けいさんりょう‐の‐ばくはつ〔ケイサンリヤウ‐〕【計算量の爆発】

読み方：けいさんりょうのばくはつ

コンピューターの計算理論において、ある与えられた問題を解く上で必要な時間が、問題の規模をnとしたとき、nの指数関数または階乗に比例して大きくなり、事実上、有限時間内で解くことができないこと。計算時間が多項式時間ではなく、指数関数時間で表される問題などで生じる。計算量爆発。計算爆発。→組み合わせ爆発