時間複雜度

計算複雜度理論 에서 時間複雜度 는 問題를 解決하는데 걸리는 時間과 入力의 函數關係를 가리킨다.

컴퓨터科學에서 알고리즘의 時間複雜度는 入力을 나타내는 文字列 길이의 函數로서 作動하는 알고리즘을 醉해 時間을 定量化하는 것이다. 알고리즘의 時間複雜度는 主로 빅-오 表記法을 使用하여 나타내며, Pan Bubilek이 빅-오 表記法은 係數와 낮은 次數의 項을 除外시키는 方法이다. 이런 方式으로 表現할 때, (例를 들면, 入力 크기를 無限大로 入力하여) 時間複雜度를 漸近的으로 描寫한다고 말한다.

例示로서, 萬若 크기 n의 모든 入力에 對한 알고리즘에 必要한 時間이 最大 (어떤 n ₀보다 크지 않은 모든 n에 對하여) 5 n ³ + 3 n 衣式을 가진다면, 이 알고리즘의 漸近적 時間複雜度는 O( n ³)이라고 할 수 있다.

時間複雜度는 基本的인 演算을 遂行하는데에 어떤 固定된 時間이 걸릴 때, 알고리즘에 依해서 遂行되는 基本演算의 個數를 세어 豫測할 수 있다. 그러므로 걸리는 時間의 總量과 알고리즘에 依해 遂行되는 基本的인 演算의 個數는 最大常數人者만큼 다르다.

알고리즘의 遂行時間은 同一 크기의 다양한 入力에 依해 달라질 수 있기 때문에, 가장 많이 쓰이는 最惡의 時間複雜度 의 알고리즘 時間을 T(n) 이라고 했을 때, 이것은 크기 n의 모든 入力에 對해 걸리는 最大의 時間 으로 定義할 수 있다.

그 다음으로 덜 흔하게 쓰이면서, 普通明確하게 敍述되는 測定方法은 平均時間複雜度 이다.

時間複雜度는 函數 T(n)의 特性에 依해 分類할 수 있다. 例를 들면, T(n)=O(n)인 알고리즘은 線型時間 알고리즘 이라고 부르며, 몇몇 M ≥ n >1에 對해 T(n)=O(M ⁿ)이고 M ⁿ=O(T(n)) 人 알고리즘은 指數時間 알고리즘 이라고 한다.

共通時間複雜度票 [ 編輯 ]

이름	複雜度種類	遂行時間 ( T ( n ))	遂行回數例示	알고리즘 例示
上水時間		O (1)	10	精髓(二進數로 表現되는)가 짝數이거나 홀數인지 決定
驛 아커만 時間 (Inverse Ackermann time)		O (α(n))		서로素集合 을 使用한 演算黨分割償還時間
反復 로그 時間 (iterated logarithmic time)		O ( log * n )
로그-로그 時間		O (log log n )		유계 優先順位 큐 를 使用한 演算黨分割償還時間 ^[1]
로그 時間	DLOGTIME	O (log n )	log n , log( n ²)	이晉探索
다항 로그 時間		poly(log n )	(log n ) ²
分數指數		O ( n ^c) where 0 < c < 1	n ^1/2, n ^2/3	k次元 트리 探索
線型時間		O ( n )	n	整列되지 않은 配列 에서 가장 작은 數 또는 가장 큰 數를 探索
"n log ^* n" 時間		O ( n log * n )		자이델 (Seidel)의 多角形三角火 알고리즘
線型 로그 時間		O ( n log n )	n log n , log n !	가장 빠른 比較整列 : 高速 푸리에 變換
2次時間		O ( n ²)	n ²	버블 整列 , 揷入整列 , 直接的合成곱
3次時間		O ( n ³)	n ³	n × n 行列 두 個의 無識한 곱셈, 偏尙關係計算
다항 時間	P	2 ^O (log n ) = poly( n )	n , n log n , n ¹⁰	線型 계획법 을 위한 카르마카(Karmarkar)의 알고리즘 , AKS 少數判別法
준 다항 時間	QP	2 ^{poly(log n )}	n ^log log n, n ^log n	有香 슈타이너 트리 問題 에 對해 잘 알려진 O(log ² n )- 近似 알고리즘
서브 指數函數 (1番째 定義)	SUBEXP	O (2 ^{n ^ε}) for all ε > 0	O (2 ^{log n ^{log log n}})	複雜度의 理論的推測을 생각했을 때, BPP 는 SUBEXP에 包含.
서브 指數函數 (2番째 定義)		2 ^o ( n )	2 ^{n ^1/3}	素因數分解 와 그래프 同型 에 對해 잘 알려진 알고리즘
指數時間 (線型指數)	E	2 ^O ( n )	1.1 ⁿ, 10 ⁿ	動的計劃法 을 使用한 外販員問題解決方法
指數時間	EXPTIME	2 ^poly( n )	2 ⁿ, 2 ^n ²	브루트 포스 探索 을 통한 連鎖行列 곱셈 의 解決方法
팩토리얼 時間		O ( n !)	n !	브루트 포스 探索 을 통한 外販員問題解決方法
二重指數時間	2-EXPTIME	2 ^{2 ^poly( n )}	2 ^2 ⁿ	프레스버거(Presburger) 算術命題의 眞僞與否決定

上水時間 (Constant time) [ 編輯 ]

萬若 어떤 알고리즘의 T ( n ) 값이 入力 크기에 拘礙받지 않는 값에 依해서 限定된다면, 이 알고리즘은 上水時間 ( O(1) 時間이라고 쓰기도 함) 이라고 말할 수 있다. 例를 들면, 單 하나의 演算이 어떤 配列에서의 要素位置를 알아내는 것을 遂行한다고 할 때, 이 要素에 接近하는 것은 常數時間이 걸린다. 그러나 順序가 定해져있지 않은 配列에서의 最小 값을 찾는 것은, 가장 작은 값을 決定하기 위해 어떤 配列에서의 各要素를 훑는 것이 必要하기 때문에 상수 時間이 아니다. 이것은 그렇기 때문에 線形時間演算이며, O( n ) 時間이 所要된다. 그러나 萬若要素들의 個數를 미리 알고있고 變化가 없다면, 이러한 알고리즘은 常數時間에 이루어질 수 있다고 말할 수 있다.

"上水時間"이라는 이름에도 不拘하고, 遂行時間 은 問題의 크기에 獨立的일 必要가 없지만 遂行時間의 上限 은 問題의 크기에 獨立的으로 制限된다. 例를 들면, " 必要하다면 a와 b를 바꿔서 a≤b가 되도록 하시오 "와 같은 것은, 時間이 이미 a≤b 條件滿足與否에 從屬的이라고 한다고 해도, 常數時間을 갖는다고 할 수 있다. 그러나 要求되는 時間이 恒常最大 t 人常數 t 가 存在하기도 한다.

아래는 常數時間 동안 遂行되는 코드의 예제이다.

int index = 5;
int item = list[index];

if(條件이 참일 때) then
    常數 時間 동안 遂行되는 어떤 演算을 實行
else
    常數 時間 동안 遂行되는 어떤 演算을 實行
for i = 1 to 100
    for j = 1 to 200
        常數 時間 동안 遂行되는 어떤 演算을 實行

萬若 T( n )이 O( 어떤 常數값 )이라면, 'T( n )은 O(1)이다'라는 것과 同等하며, 이것을 標準表記法으로 使用한다.

로그 時間 (Logarithmic time) [ 編輯 ]

萬若 T( n ) = O(log n ) 이라면, 이 알고리즘은 로그 時間이 걸린다고 말할 수 있다. 컴퓨터가 이진수 시스템을 使用하기 때문에, 로그는 밑을 大部分 2로 使用한다. (卽, log ₂n , 때때로는 log n 이라고 쓰임.) 그러나, 로그의 밑이 變할 때, log _an 와 log _bn 는 오로지 上水勝數 에 따라서만 달라지며 이것은 빅-오 表記法에서는 버림한다; 그러므로 O(log n )은 로그의 밑과 相關없이 로그 時間 알고리즘에 對한 標準表記法이 된다.

로그時間이 걸리는 알고리즘은 이진트리에서의 演算에서나 또는 李瑱探索에서 찾아볼 수 있다.

O(log n )알고리즘은 인스턴스當演算이 各 인스턴스에 對해서 最大限 줄어드는 것이 必要하기 때문에, 높은 效率을 갖고 있다고 여긴다.

이런 타입의 가장 쉬운 예제 알고리즘은, 文字列을 折半으로 쪼개어 그 오른쪽의 文字列을 다시 또 折半으로 쪼개고, 이를 反復하는 알고리즘으로 생각할 수 있다. 이 알고리즘은 우리가 各各의 出力以前에 文字列을 折半으로 나누기 때문에, O(log n)時間 (n은 文字列의 길이) 이 所要된다. 이것은 出力回數를 증가시키기 위해서는 文字列의 길이를 두倍로 늘려야 함을 의미한다.

// 文字列의 오른쪽 折半을 再歸的으로 出力하는 函數.

var
 right
 =
 function
(
str
){

    var
 length
 =
 str
.
length
;


    // Helper function

    var
 help
 =
 function
(
index
){


        //再歸呼出 部分: 오른쪽 折半을 出力

        if
(
index
 <
 length
){


            //인덱스로 配列 끝까지 文字 出力

            console
.
log
(
str
.
substring
(
index
,
 length
));


            //再歸 呼出 部分: 오른쪽 折半에 對해서 help를 呼出

            help
(
Math
.
ceil
((
length
 +
 index
)
/
2
));

        }


        // Base Case: Do Nothing

    }

    help
(
0
);

}

다항 로그 時間 (Polylogarithmic time) [ 編輯 ]

萬若 T( n ) = O((log n ) ^k) 이라면, 이 알고리즘은 어떤 常數 k 에 對해 다항 로그 時間 동안 遂行된다고 말할 수 있다. 例를 들면, 行列 체인 곱은 竝列 랜덤 接近機械 (Parallel Random Access Machine: PRAM)에서 다항 로그 時間에 解決할 수 있다.

서브-線形時間 (Sub-linear time) [ 編輯 ]

萬若 T( n ) = o( n ) 이면, 이 알고리즘은 서브-線形時間 동안 作動된다고 말할 수 있다. 特히 이 알고리즘은 위에서 定義된 時間複雜度들을 가진 것들을 包含하며, O( n ^1/2) 인 Grover 探索 알고리즘을 包含한다.

서브-線形時間 동안 作動하는 典型的인 알고리즘들은 竝列 프로세싱, 非標準 프로세싱을 使用하거나, 入力構造에 對한 保障된 家庭을 갖는다. 그러나 文字列의 처음부터 log(n)番째 비트 位置에서의 한 個의 비트를 갖는 모든 文字列의 集合果 같은 形式言語 는 入力의 모든 비트에 從屬的日 수 있고, 서브-線形時間에 가깝게 計算될 것이다.

서브-線形時間 알고리즘이라는 特定用語는 알고리즘들이 典型的인 一列機械 모델에서 作動하며 入力에 對해 于先家庭을 許容하지 않는다는 點에서, 위와는 다른 알고리즘을 말한다. 그러나 이 알고리즘들은 랜덤火 될 수 있고, 거의 가장 些少한 程度의 태스크들에 對해서는 반드시 랜덤화되어야만 한다.

이러한 알고리즘은 반드시 全體入力을 읽지 않고 結果를 提供해야 하기 때문에, 이것의 특별함은 詳細明細는 入力에 許容되는 接近에 宏壯히 從屬的이다. 普通 b ₁,..., b _k 로 表現되는 이진 文字列에 對해서, 알고리즘이 어떤 i에 對해 b _i의 값을 要請하거나 얻는데 O(1) 時間이 걸린다고 假定할 수 있다.

서브-線形時間 알고리즘은 普通 랜덤化되며, 오로지 大略的인 解決策만을 提供해준다. 事實, 0萬 가지는 이진 文字列의 特性은 (非近似的인) 서브-線形時間 알고리즘에 依해서 決定될 수 없다는 것을 쉽게 證明할 수 있다. 서브-線形時間 알고리즘은 特性 테스팅 (Property testing) 調査에서 자연스럽게 나타난다.

線型時間 (Linear time) [ 編輯 ]

萬若時間複雜度가 O(n)이면, 이 알고리즘은 O(n)時間或은 線形時間을 갖는다고 말할 수 있다. 略式으로 充分히 큰 入力 크기에 對해서 遂行時間이 入力 크기에 따라 線形的으로 增加함을 意味한다. 例를 들어, 리스트의 모든 要素를 더하는 프로시저는 리스트의 길이에 比例하는 時間을 要求한다. 이러한 說明은 遂行時間이 特히 작은 n의 값에 對해, 正確한 線形的인 比例形態로부터 相當히 偏差를 가질 수 있기 때문에 多少不正確하다.

種種線形時間은 알고리즘의 理想的인 特性으로 여겨진다. 많은 硏究者들은 線形時間이나 그보다 더 좋은 알고리즘을 만드는 것을 硏究해왔다. 이러한 硏究는 소프트웨어와 하드웨어的인 方法 모두를 包含한다. 數學的으로, 標準計算 모델을 使用해 線形時間을 絶對 얻을 수 없는 알고리즘들은 하드웨어的인 觀點에서 線形時間 동안 實行될 수 있다. 이것을 提供하는 竝列式方法을 利用하는 하드웨어 技術이 存在하며, 例로 content-addressable 메모리와 같은 것이 있다. 이러한 線形時間槪念은 Boyer-Moore 알고리즘과 Ukkonen 알고리즘과 같은 文字列 매칭 알고리즘에서 使用된다.

類似線形時間 (Quasilinear time) [ 編輯 ]

어떤 量의 上水 k 에 對해서 T(n) = O( n log ^kn ) 裏面, 이 알고리즘은 類似線形時間 동안 實行된다고 말할 수 있다; 線形로그 時間은 k =1人境遇이다. 소프트-오 表記法을 使用하면, 이 알고리즘은 O( n )이다. 類似線形時間 알고리즘은 모든 ? < 0 에 對해서 O( n ^1+?)이고, 그러므로 1보다 嚴格하게 큰 指數를 가진 n에서의 모든 多項式 보다 빠르다.

類似線形時間에서 實行되는 알고리즘들은, 線形 로그 알고리즘에 덧붙여 다음을 包含한다.

In-place 合倂整列, O( n log ²n )
퀵 整列 , O( n log n ), 랜덤化된 버전에서는 最惡의 境遇入力에 對한 平均에서의 線型로그 時間을 遂行時間으로 갖는다.
힙 整列 , O( n log n ), 合倂整列 , intro整列, 李瑱 트리 整列, smooth整列, patience 整列等에서의 最惡의 境遇.
高速 퓨리에 變換, O( n log n )
Monge 配列計算, O( n log n )

線型 로그 時間 (Linearithmic time) [ 編輯 ]

線型 로그 時間은 指數 k 가 로그 港의 하나와 同一한 類似線形時間의 特異한 境遇이다. 線型 로그 函數는 n log n 形態의 函數卽, 선형과 로그抗議 곱이다. 萬若 T( n ) = O( n log n ) 이라면, 알고리즘은 線形로그 時間 동안 實行된다고 말할 수 있다. 그러므로 線形로그 項은 線形港 보다는 빠르게 增加하지만, 1보다 큰 指數를 가진 n의 多項式보다는 느리다.

많은 境遇에, n log n 遂行時間은 簡單히 Θ(log n ) 演算의 n 倍遂行時間의 結果를 가진다. 例를 들면, 李瑱 트리 整列은 n 크기의 配列各要素를 하나하나 揷入하여 李瑱 트리를 만든다. 自家均衡李瑱探索 트리의 揷入 연산은 O(log n )時間이 걸리기 때문에, 全體 알고리즘은 線形 로그 時間이 걸린다.

比較整列은 Stirling 近似에 依해 log( n !) = Θ( n log n )이기 때문에, 最惡의 境遇比較回數가 最小線形 로그가 必要하다. 그리고 또한 T( n ) = 2T( n /2) + O( n ) 再歸關係에서 頻繁히 나타난다.

서브-二次時間 (Sub-quadratic time) [ 編輯 ]

萬若 T( n ) = o( n ²)이면, 서브-二次時間의 알고리즘이라고 말할 수 있다.

例를 들면, 簡單히 比較基盤整列 알고리즘은 二次 (例를 들면, 揷入整列 )이지만 더 深化된 알고리즘은 서브-二次 (例를 들면, 쉘 整列 )인 것을 찾을 수 있다. 어떤 汎用貞烈도 線形時間에 遂行될 수 없지만, 二次에서 서브 이車路의 變更은 대단히 現實的으로 重要하다.

다항 時間 (Polynomial time) [ 編輯 ]

萬若 어떤 常數 k 에 對해 T( n ) = O( n ^k)와 같이, 入力 크기에 어떤 다항 表現의 上限을 가지고 遂行이 되는 알고리즘이 있다면, 그 알고리즘은 다항 時間을 가진다고 말할 수 있다. 決定論的多項時間 알고리즘 (deterministic polynomical time algorithm) 이 存在하는지에 對한 問題들은 複雜度 클래스 P에 屬하며, 이 複雜度 클래스 P 는 計算複雜度理論分野에서 核心을 차지한다. Cobham 論題는 다항 時間이 "追跡可能한", "實現可能한", "效率的인" 또는 "빠른" 과 같은 同義語를 갖는다고 言及한다.

몇 가지 다항 時間 알고리즘의 例를 들면,

精髓 n 에 對한 選擇整列 알고리즘 이 常數 A 에 對해서 $An^{2}$ 個의 演算을 遂行한다. 그렇다면 이것은 $O(n^{2})$ 의 時間 동안 遂行되며, 多項時間 알고리즘이라고 할 수 있다.
모든 基本算術演算 ( 덧셈 , 뺄셈 , 곱셈, 나눗셈 그리고 比較)는 多項時間 동안 이루어진다.
그래프에서의 最大 매칭은 다항 時間 동안 찾을 수 있다.

强力한 다항 時間과 弱한 多項時間 [ 編輯 ]

一部文脈에서는, 特히 最適化의 境遇, 强力한 다항 時間 과 弱한 다항 時間 알고리즘 사이에 差別點이 存在한다. 이 두 槪念은 萬若 알고리즘의 入力이 精髓로 構成되어 있을 때만 關聯이 있다.

强力한 多項時間은 計算의 算術 모델에서 定義된다. 이 算術 모델에서 基本算術演算은 被演算子의 크기에 相關없이 遂行하는데 單位時間段階가 所要된다. 알고리즘은 아래와 같은 境遇, 强力한 다항 時間에 遂行된다고 할 수 있다.

計算의 算術 모델에서 演算의 回數는 入力 인스턴스의 精髓個數를 가지고 多項式으로 境界값을 갖는다.
알고리즘의 空間은 入力 크기가 多項式으로 境界값을 가진다.

위와 같은 特性을 가진 모든 알고리즘들은 튜링 머신에서 算術演算을 遂行하는 적합한 알고리즘을 使用해 算術演算을 交替하는 것으로 多項時間 알고리즘火 할 수 있다. 萬若 두 番째의 要求事項이 充足되지 않으면, 多項時間 알고리즘化의 可能性은 더以上滿足하지 않는다. 튜링 머신에서 n에 比例하는 空間을 차지하는 淨水 $2^{n}$ 이 주어졌을 때, 反復 제곱을 使用해서 n회 곱한 $2^{2^{n}}$ 을 計算하는 것이 可能하다. 그러나 $2^{2^{n}}$ 을 表現하는 데 쓰이는 空間은 $2^{n}$ 에 比例하므로, 入力을 表現하는데 쓰이는 空間은 다항 空間이기 보다는 指數空間이다. 그러므로 튜링 머신에서 多項時間에 이 計算의 結果값을 導出해내는 것은 不可能하지만, 다항 時間을 갖는 많은 算術演算을 가지고 이것을 計算하는 것은 可能하다.

뒤집어 생각해보면, 2陣 인코딩된 入力 길이로 多項式境界가 지어진 많은 튜링 머신 段階에서 作動하는 알고리즘들이 있다. 그러나, 入力數의 個數로 多項式境界가 지어진 많은 算術演算들은 採擇하지 않는다. 두 整數의 最大公約數를 計算하기 위한 有클리디안 알고리즘은 그 하나의 例이다. 알고리즘의 遂行時間이 주어진 두 個의 整數 a와 b에 對해서 $O((\log a+\log b)^{2})$ 튜링 머신 段階로 境界를 갖는다. 表現의 크기가 大略的으로 $\log a+\log b$ 일 때, a와 b의 李瑱表現의 크기가 다항 크기를 갖는다. 同時에, 算術演算個數는 入力에서의 精髓個數로 制限될 수 없다. (이 때의 入力값은 常數이고, 入力에서의 정수는 恒常 2個이다.) 後者의 觀測으로 因해, 强力한 다항 時間에서 이 알고리즘은 作動할 수 없다. 이것의 實際實行時間은 a와 b의 크기에 依存하며, 入力값에서 精髓個數에도 依存한다.

다항 時間에 作動하지만 强力한 다항 時間은 아닌 알고리즘은 弱한 다항 時間 동안에 作動한다고 말할 수 있다. 弱한 다항 時間 알고리즘으로 알려져있는 問題中에 가장 有名한, 하지만 强力한 다항 時間 알고리즘은 아닌 예제는 線型 계획법 이다. 弱한 多項時間은 有史 다항 時間과 헷갈려서는 안된다.

複雜度 클래스 [ 編輯 ]

다항 時間의 槪念은 計算複雜度理論에서 여러 가지 複雜度 클래스로 連結된다. 몇 가지 重要한 다항 時間이 使用되어 定義된 클래스들은 다음과 같다.

P: 다항 時間 동안 決定的 튜링 머신에서 解決할 수 있는 決定問題의 複雜度 클래스
NP: 다항 時間 동안 非決定的 튜링 머신에서 解決할 수 있는 決定問題의 複雜度 클래스
ZPP: 다항 時間 동안 確率的 튜링 머신에서 0의 에러確率로 解決할 수 있는 決定問題의 複雜度 클래스
RP: 다항 時間 동안 確率的 튜링 머신에서 단방향 에러를 가지고 解決할 수 있는 決定問題의 複雜度 클래스
BPP: 다항 時間 동안 確率的 튜링 머신에서 兩方向 에러를 가지고 解決할 수 있는 決定問題의 複雜度 클래스
BQP: 다항 時間 동안 兩者 튜링 머신에서 兩方向 에러를 가지고 解決할 수 있는 決定問題의 複雜度 클래스

P는 머신 모델 變化의 側面에서 强健한 決定的 머신에 對해 가장 작은 時間複雜度 클래스를 나타낸다. 모든 주어진 抽象 머신은 該當 머신에 對해 다항 時間 동안 解決할 수 있는 問題에 該當하는 複雜度 클래스를 갖는다.

超多項時間 (Superpolynomial time) [ 編輯 ]

萬若 T(n)李 모든 多項式 위에서 境界를 갖지 않는다면, 이것을 超多項時間이 걸리는 알고리즘이라고 말할 수 있다. 이것은 모든 常數 c 에 對해서 n이 入力 파라미터 일 때, ω( n ^c)時間을 갖는다. (一般的으로, 이 n은 入力값에서의 비트 個數를 뜻한다.)

例를 들면, 크기 n 의 入力값에 對해 2 ⁿ段階實行되는 알고리즘은 超多項時間을 要求한다. (좀 더 正確히 말하자면, 指數時間이다.)

指數資源을 使用하는 알고리즘은 分明하게 超多項이지만, 어떤 알고리즘들은 매우 弱한 超多抗日 뿐이다. 例를 들면, Adelman-Pomerance-Rumely 疏水性 테스트가 n비트의 入力에 對해서 n ^{O(log log
n
)}의 時間 동안 實行된다; 이것은 充分히 큰 n 에 對해서 모든 다항 時間보다 빠르다. 하지만 入力 크기는 반드시 이것이 작은 指數의 多項式에 依해 支配될 수 없기 前에 非現實的인 크기가 되어야만 한다.

超多項時間을 必要로하는 알고리즘은 複雜度 클래스 P밖에 놓인다. Cobham 論題는 이런 알고리즘이 非現實的임을 받아들인다. P vs. NP問題가 解決되지 않았기 때문에, 어떤 NP完備問題도 다항 時間 동안 實行될 수 있다고 알려진 것이 없다.

준-다항 時間 (Quasi-polynomial time) [ 編輯 ]

준-다항 時間 알고리즘은 다항 時間보다 느리지만 指數時間보다는 느리지 않은 알고리즘이다. 준-다항 時間 알고리즘의 最惡의 境遇時間은, 어떤 固定된 $c>0$ 에 對해 $2^{O((\log n)^{c})}$ 값을 갖는다. 精髓因數分解에 對해 $2^{{\tilde {O}}(n^{1/3})}$ 時間이 所要되는 가장 잘 알려진 古典 알고리즘人 代表數字領域 거르기 (general number field sieve)는 實行時間이 固定된 c에 對해서 $2^{O((\log n)^{c})}$ 로 나타낼 수 없기 때문에 준-다항시간 알고리즘이 아니다. 萬若 준-다항 時間 알고리즘 正義에서의 常數 c가 1과 같다면, 우리는 多項時間 알고리즘을 얻을 수 있고, 1보다 작다면, 서브 線形時間 알고리즘을 얻을 수 있다.

준-다항 時間 알고리즘은 典型的으로 NP-難題問題에서 다른 問題로의 還元에서 생길 수 있다. 例를 들면, NP-難題問題 하나가 3SAT이고, 이것을 다른 問題 B로 바꾸지만 이 問題의 크기는 $2^{O((\log n)^{c})}$ 이다. 이런 境遇, 이 還元은 問題 B가 NP-難題임을 證明할 수 없다; 이 還元은 萬若 3SAT에 對한 준-다항 時間 알고리즘이 없다면, 團地 B에 符合하는 多項時間 알고리즘이 없다는 것만을 보여줄 수 있다.

비슷하게, 우리가 알고있는 준-다항 時間 알고리즘은 몇가지 있지만, 다항 時間 알고리즘은 없다. 이런 問題는 近似 알고리즘에서 發生한다; 가장 有名한 예제는 方向性 Steiner 트리 問題이고, 이 問題는 頂點個數가 n인 트리에서 $O(\log ^{3}n)$ 의 近似因子를 達成하는 준-다항 時間近似 알고리즘이다. 그러나, 다항 時間 알고리즘의 存在를 보여주는 것은 열린 問題이다.

多項時間은 아니지만, 준-다항 時間인 다른 解決計算問題들은 Laszlo Babai에 依한 그래프 同型問題와 클릭의 合集合과 랜덤 그래프에서 가장 큰 클릭을 찾는 目標를 가지고 있는 planted clique 問題가 있다.

준-다항 알고리즘이 解決可能하긴 하지만, planted clique 問題는 다항 時間解決方法이 없다고 推測된다; 이 planted clique의 境遇는 計算 게임理論, 特性 테스팅, 機械學習에서의 다른 여러 問題들의 어려운 程度를 證明하기 위한 計算難題家庭 (computational hardness assumption) 으로서 使用된다.

QP 複雜度 클래스는 모두 준-다항 時間 알고리즘으로 이루어져있다. 이것은 다음의 DTIME으로 定義된다.

${\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{(\log n)^{c}})$

NP-完備問題와의 聯關 [ 編輯 ]

複雜度理論에서, 未解決問題인 P vs. NP問題는 NP問題 모두가 다항 時間 알고리즘인지의 與否를 묻는다. 3SAT問題等과 같은, 모든 알려진 NP-完備問題 알고리즘들은 指數時間이 걸린다. 實際로, 서브-指數時間 알고리즘을 가지지 않는 많은 自然 NP-完備問題들에 對해 推測이 되어왔다. 여기서 "서브-指數時間"은 아래 두番째 定義에 標示되어 있다. (反面, 隣接行列方法을 使用한 많은 그래프 問題들은 入力 크기가 頂點個數의 제곱이기 때문에, 서브 指數時間에 解決이 可能하다.)

이러한 k-SAT問題에 對한 家庭은 指數時間家庭 으로 알려져있다. NP-完備問題가 준-다항 時間 알고리즘을 갖고있지 않다고 생각되기 때문에, 近似 알고리즘 領域에서 近似的이지 않은 結果는 NP-完備問題가 준-다항 時間 알고리즘을 갖지 않는다는 家庭을 만든다. 例를 들면, 集合 덮개 問題의 非近似的結果와 같은 것이다.

서브-指數時間 (Sub-exponential time) [ 編輯 ]

서브-指數時間이라는 用語는 어떤 알고리즘의 遂行時間이 多項時間보다 빠르지만 顯著히 指數時間 보다는 작게 增加하는 것을 表現하는데 使用한다. 이러한 點에서, 서브-指數時間 알고리즘은 오로지 指數 알고리즘보다는 多少 더 追跡이 可能한 問題들이다. "서브-指數時間"의 正確한 定義는 同意가 되어있지 않고, 아래의 두 正義가 폭넓게 使用되고 있다.

첫 番째 定義 [ 編輯 ]

萬若 어떤 알고리즘이 주어진 多項式보다 작게 增加하는 遂行時間 안에 解決될 수 있다면, 그 問題는 서브-指數時間이 걸린다고 말한다. 더 正確하게는, 모든 ε > 0에 對해서 O(2 ^{n
^ε}) 時間에 問題를 解決하는 알고리즘이 存在한다면, 서브-指數時間問題이다. 이러한 問題들은 다음과 같이 DTIME으로 定義되는 SUBEXP 複雜度 클래스를 갖는다.

{\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)

서브-指數表記法은, 入力 값의 部分이 아니라는 點과 各 ε이 該當問題만의 알고리즘을 갖고있다는 點에서 ε에 對해 非均一하다.

두 番째 定義 [ 編輯 ]

어떤 사람들은 2 ^o(
n
) 로 서브-指數時間을 定義한다. 이 定義는 서브-指數時間의 첫番째 正義보다는 더 큰 實行時間이 許容된다. 예제로는, 精髓因數分解하는 가장 잘 알려진 古典 알고리즘人 代表數字領域 거르기 (general number field sieve) 가 있으며, 이것의 實行時間은 入力 크기가 n의 길이를 가질 때, $2^{{\tilde {O}}(n^{1/3})}$ 를 갖는다. 또 다른 예제는 그래프 同型問題 로 $2^{O({\sqrt {n\log n}})}$ 時間이 所要된다.

이것은 알고리즘이 인스턴스의 크기, 頂點의 個數 또는 幹線의 個數에서 서브-指數가 되는 것을 許容하는 알고리즘인지의 與否에 따라 다르다는 것을 銘心하자. 媒介變數火複雜度 에서는, 이러한 差異點이 決定問題의 $(L,k)$ 페어와 人者 k를 考慮하는 것으로서 분명해진다. SUBEPT는, 入力 크기 n일 때 多項이며 k에 對해 서브-指數時間遂行되는 모든 媒介變數火問題의 複雜度 클래스이다.

{\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).

더 正確하게 SUBEPT는 計算可能한 函數 $f:\mathbb {N} \to \mathbb {N}$ with $f\in o(k)$ 에 對해서 모든 媒介變數火問題 $(L,k)$ 의 複雜度 클래스이며, 알고리즘은 $2^{f(k)}\cdot {\text{poly}}(n)$ 時間 동안 L을 決定한다.

指數時間 (Exponential time) [ 編輯 ]

poly(n)李 n에서의 어떤 多項式이라고 할 때, 萬若 T(n)李 2 ^poly(n)로 上限이 定해진다면, 이 알고리즘은 指數時間을 갖는다고 말할 수 있다. 더 形式的으로, 萬若 T(n)李 어떤 常數 k에 對해서 $O(2^{n{^{k}}})$ 를 갖는다면, 指數時間을 갖는다. 決定的 튜링 머신에 對해 指數時間 알고리즘人問題들은 EXP로 알려져있는 複雜度 클래스를 만든다.

$EXP=\bigcup _{c\in \mathbb {N} }DTIME({2^{n{^{c}}}})$

가끔 指數時間은 指數가 最大 n의 線形函數일 때, T(n) = 2 ^O(n)을 갖는 알고리즘으로 使用되기도 하며, 複雜度 클래스 E를 表現한다.

$E=\bigcup _{c\in \mathbb {N} }{DTIME}(2^{cn})$

二重指數時間 (Double exponential time) [ 編輯 ]

poly(n)李 n에서의 어떤 多項式이라고 할 때, 萬若 T(n)李 2 ^2poly(n)로 上限이 定해진다면, 이 알고리즘은 二重指數時間을 갖는다고 말할 수 있다. 이러한 알고리즘들은 2-EXPTIME 複雜度 클래스에 屬한다.

${\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{c}}}\right)$

잘 알려진 二重指數時間 알고리즘은 다음을 包含한다:

Presburger 演算을 위한 決定過程
(最惡의 境遇에서) Grobner basis 計算
닫힌 失手領域에 對한 限定記號除去 (Quantifier elimination)는 最小二重指數時間이 걸린다.

같이 보기 [ 編輯 ]

各州 [ 編輯 ]

↑ Mehlhorn, Kurt; Naher, Stefan (1990). “Bounded ordered dictionaries in O(log log N) time and O(n) space”. 《Information Processing Letters》 35 (4): 183?189. doi : 10.1016/0020-0190(90)90022-P .

[1] Mehlhorn, Kurt; Naher, Stefan (1990). “Bounded ordered dictionaries in O(log log N) time and O(n) space”. 《Information Processing Letters》 35 (4): 183?189. doi : 10.1016/0020-0190(90)90022-P .

[1]

共通 時間 複雜度 票 [ 編輯 ]

上水 時間 (Constant time) [ 編輯 ]