指数関数時間

デジタル大辞泉

しすうかんすう‐じかん〔シスウクワンスウ‐〕【指数関数時間】

読み方：しすうかんすうじかん

コンピューターの計算理論において、問題を解く上で必要な計算時間が、問題の規模をn、定数をkとしたとき、nの指数関数すなわちkⁿで表されるもの。問題の規模とは組み合わせの要素や繰り返しの数を指し、nが大きくなるに従い、計算時間が爆発的に増える。指数時間。→多項式時間 →計算量の爆発

ウィキペディア

指数関数時間

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/21 08:41 UTC 版)

指数関数時間（しすうかんすうじかん）あるいは指数時間（しすうじかん）とは、計算理論において指数関数を用いてあらわされる計算時間。計算複雑性理論では指数関数時間で解ける判定問題のクラスのことをクラス EXPTIME（あるいは EXP）という。