![](https://scientia-potentia-est.com/wp-content/uploads/2023/11/Time-Complexity.png)
目錄
測量複雜度
- Worst-case analysis
- Average-case analysis
定義一個M是Deterministic Turing Machine並且會根據輸入決定停止
- 規範M的執行時間或者時間複雜度可以表示成一個function
,其中
是指M輸入長度n的最大步驟數量
- 如果
是M的執行時間,可以表示M執行
的時間並且稱M是一個
時間的Turing Machine
Big-O以及Small-o漸進符號
定義:,如果存在一個正整數c(通常是個常數)以及
使得任何的
範例:,
顧名思義就是存在一組時間複雜度是目前的執行時間上限
定義:, 表示
if
範例:
![Rendered by QuickLaTeX.com \sqrt(n) = o(n), n^{2} = o(n^{3}), nloglogn = o(nlogn)](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-3df7ab23bd9e0d7fd774ae18a375b5a1_l3.png)
定義:
![Rendered by QuickLaTeX.com t: N \rightarrow N](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-5f562136218b0f2bf9013e46c0ae6c21_l3.png)
![Rendered by QuickLaTeX.com TIME(t(n))](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-c2c847957b2649a7609c3c14730974df_l3.png)
![Rendered by QuickLaTeX.com O(t(n))](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-6c6f7bb3b4cf2a834c731321ed7c4e9c_l3.png)
不同的模型設計之下會有不同的複雜度關聯
定理:
![Rendered by QuickLaTeX.com t(n):](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-4b257927ec4ab027b92d335559a5efa6_l3.png)
![Rendered by QuickLaTeX.com \geq n](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-072f76b42a550fb1418c6c9281a0a7f0_l3.png)
![Rendered by QuickLaTeX.com t(n)](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-3fb802cdca7ecc0fff29bd12dc38043a_l3.png)
![Rendered by QuickLaTeX.com O(t^{2}(n)](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-7b1be0c966569f80b2e4954f79d317a0_l3.png)
定理:
![Rendered by QuickLaTeX.com t(n):](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-4b257927ec4ab027b92d335559a5efa6_l3.png)
![Rendered by QuickLaTeX.com \geq n](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-072f76b42a550fb1418c6c9281a0a7f0_l3.png)
![Rendered by QuickLaTeX.com t(n)](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-3fb802cdca7ecc0fff29bd12dc38043a_l3.png)
![Rendered by QuickLaTeX.com 2^{O(t(n))}](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-297d90ace19e6a3f1d04d4a6b1ac90e1_l3.png)
P類別
P是指language的類別能夠被deterministic single-tape Turing Machine在多項式時間(polynomial time)內被決定(decidable),換言之可以表示成:
舉例來說:
有一組
![Rendered by QuickLaTeX.com PATH](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-b5715bd5b9b215f5220d8552182d56d4_l3.png)
![Rendered by QuickLaTeX.com G, s, t](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-9aa8bc521d5ab2a21bdf6c5c59ac76da_l3.png)
![Rendered by QuickLaTeX.com G](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-50d68e949db1e2a6cc534177402bfb82_l3.png)
![Rendered by QuickLaTeX.com s](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-13a0857aae01c2b0572b77c46fbdae9d_l3.png)
![Rendered by QuickLaTeX.com t](https://scientia-potentia-est.com/wp-content/ql-cache/quicklatex.com-821456a7f84a4a58de7acb681c9b394d_l3.png)
定義:
另外像是 = {<
>|
為互質},也同樣定理:
NP類別
Hamiltonian path是一組有向圖存在一條有向路徑可以從
走到
且每個點只經過一次
= {<
>|G是一個有向圖存在一條Hamiltonian path從
到
}
![](https://scientia-potentia-est.com/wp-content/uploads/PNP/HAMPATH.png)
可以觀察到存在指數時間(exponential time)的演算法來解決HAMPATH問題,而要驗證HAMPATH問題的話只要給路徑的點跟線就可以在多項式時間裡驗證 = {
, 對於所有的整數
},找兩個整數相乘在一起的稱作合成數
,可以看到如果有給
這兩個通常稱作certificate(證據)的話就可以在多項式時間內驗證合成數
但要注意也並不是每個問題都能夠在多項式時間裡驗證
定義:存在一個演算法針對language A的驗證者(verifier) V,其中針對某些字串
- 一個多項式時間的verifier執行驗證長度
的字串在多項式時間內
- 一個language A是多項式可驗證的話代表這是一個多項式時間的verifier
- 一個verifier使用額外的資訊
來驗證字串
屬於A的集合成員
- C: 證據(certificate)或者可以用來證明屬於A的集合成員
定義:NP是一個擁有多項式時間驗證者的language集合,代表可以在多項式時間內驗證完,但不保證能夠在多項式時間內找出答案
NP: Non-deterministic Polynomial time
定義:是一個language可以被Non-Deterministic TM在
時間內被決定(decided)
定理:一個language如果在NP裡面的話若且唯若會被Non-deterministic polynomial time Turing Machine被決定(decided)
證明::使
以及證明A會被NTM N所決定(decided).
根據NP的定義讓V是一個多項式時間驗證者針對A
首先假設V可以對輸入長度n的執行驗證時間在的時間內
開始來建構這個N:
N = 可以輸入長度n的字串
- Non-deterministically去猜長度
的字串c
- V執行驗證猜的這個字串
- 如果V可以接受,輸出ACCEPT,反之亦然,輸出REJECT
:假設A可以被NTM N在多項式時間內所決定(decided)並且建構出多項式時間驗證者V功能如下:
- 模擬N輸入
,處理c的每一個符號像是Non-deterministic的方法一樣
- 如果Non-deterministic的branch可以accept,輸出ACCEPT,反之輸出REJECT
推論:
NP問題範例
定義:clique是一個無向圖,而這個圖內每兩個點(node)必定存在一條邊(edge)
- 一個k-clique代表clique裡面包含k個點(nodes)
![](https://scientia-potentia-est.com/wp-content/uploads/PNP/5Clique.png)
定義:CLIQUE = {<>|
是一個無向圖擁有k-clique}
- 定義:CLIQUE屬於NP
證明:
N = 輸入是一個圖:
- Nondeterministically猜一組
裡有
個nodes的子集合
- 測試
是否包含所有的邊都連接這條
- 如果包含的話輸出ACCEPT,反之輸出REJECT
定義:SUBSET-SUM = {以及對於某些
}
例如:<{4, 11, 16, 21, 27}, 25} SUBSET-SUM,
,可以注意到
跟
可以是多組子集合 定義:SUBSET-SUM
NP 證明:N = 輸入
- Non-deterministically猜一個S裡面的子集合c
- 測試
是否是一個可以加總出
的集合
- 如果以上兩點都成功就輸出ACCEPT,反之輸出REJECT
所以我們稍微做個小結
P = 問題能夠被快速(polynomial)決定(decided)出來結果的language類別
NP = 問題能被快速(polynomial)驗證(verified)出來結果的language類別
而電腦科學從1950年開始發展至今一直都還沒有嚴謹證明出來的Open Problem
P到底等不等於NP?