計算量の問題で指数関数時間のアルゴリズムという場合には、解くべき問題のサイズ nに対して処理時間が多項式時間では収まらず指数関数的に増加してしまう計算方法を指す。
ある問題について、その問題を解くためのあるアルゴリズムが計算を終えるまでの時間が、問題のサイズ nに対して m(n ) であったとしよう。
●m (n ) = Ω(cn)を満たすc >1
●m (n ) = O(dn)を満たすd
この2つが存在するとき、このアルゴリズムは指数関数時間のアルゴリズムであるという。
ただし、ΩやOはO記法である。
