指数関数時間
提供: miniwiki
指数関数時間（しすうかんすうじかん）あるいは指数時間（しすうじかん）とは、計算理論において指数関数を用いてあらわされる計算時間。計算複雑性理論では指数関数時間で解ける判定問題のクラスのことをクラス EXPTIME（あるいは EXP）という。
一般に指数関数時間やその以上のアルゴリズムは時間がかかりすぎるので実用には適さない。そのようなアルゴリズムは特殊な場合にしか使われない。
定義
計算量の問題で指数関数時間のアルゴリズムという場合には、解くべき問題のサイズ n に対して処理時間が多項式時間では収まらず指数関数的に増加してしまう計算方法を指す。
ある問題について、その問題を解くためのあるアルゴリズムが計算を終えるまでの時間が、問題のサイズ n に対して m (n ) であったとしよう。
- m (n ) = Ω(cn)を満たすc > 1
- m (n ) = O(dn)を満たすd
この2つが存在するとき、このアルゴリズムは指数関数時間のアルゴリズムであるという。
ただし、ΩやOはO記法である。