時間複雜性
在理論計算機科學中，時間複雜性是描述運行算法所需的計算機時間量的計算複雜性。時間複雜性通常是通過計算算法執行的基本操作數量來估計的，並認為每個基本操作都需要固定的時間來執行。因此，算法所花費的時間和基本操作的數量被視為通過恆定因素相關。
由於算法的運行時間可能會在相同大小的不同輸入之間有所不同，因此通常認為最壞情況的時間複雜性，這是給定尺寸輸入所需的最大時間。平均案例複雜性不太常見，通常是明確指定的，這是給定尺寸輸入的時間的平均時間（這是有道理的，因為只有有限數量的給定大小的可能輸入）。在這兩種情況下，時間複雜性通常都表示為輸入大小的函數。由於通常難以準確計算此功能，並且通常不會出現小輸入的運行時間，因此當輸入大小增加時，通常關注複雜性的行為，即復雜性的漸近行為。因此，時間複雜性通常使用大o符號表示，通常是
算法複雜性根據大符號中出現的函數類型進行分類。例如，具有時間複雜性的算法
普通時間複雜性表
下表總結了一些常見的時間複雜性。在表中， poly（ x ）= x o （1） ，即x中的多項式。
| 姓名 | 複雜性類 | 運行時間（ t （ n ） ） | 跑步時間的示例 | 示例算法 |
|---|---|---|---|---|
| 恆定時間 |  | 10 | 在排序的數字中找到中位數。 計算（-1） n | |
| 倒數ackermann時間 |  | 使用不連接集的每個操作攤銷時間 | ||
| 迭代的對數時間 |  | 週期的分佈著色 | ||
| log-logarithmic |  | 使用有限的優先級隊列，每次操作攤銷時間 | ||
| 對數時間 | dlogtime |  |  , | 二進制搜索 |
| 聚集體時間 |  |  | ||
| 分數力量 |  在哪裡 |  , | 在KD-Tree中搜索範圍 | |
| 線性時間 | | n ，，  | 在未分類的陣列中找到最小或最大的物品。 | |
| “ n log-star n”時間 |  | Seidel的多邊形三角算法。 | ||
| 線性時間 | |  , | 最快的比較排序 | |
| 準線性時間 |  |  | 多點多項式評估 | |
| 二次時間 |  |  | 氣泡排序，插入排序，直接卷積 | |
| 立方時間 |  |  | 幼稚的乘法 矩陣計算部分相關。 | |
| 多項式時間 | P |  |  , | Karmarkar的線性編程算法 |
| 準多項式時間 | QP |  |  , | 最著名的O （log 2 n ） - 定向施泰納樹問題的近似算法，最著名的奇偶校驗求解器，最著名的圖形同構算法 |
| 亞指數時間 （第一個定義） | SubExp |  對全部 | 包含BPP ，除非出口時間（見下文）等於MA 。 | |
| 亞指數時間 （第二定義） |  |  | 整數分解的最佳經典算法 以前是圖形同構的最佳算法 | |
| 指數時間 （帶線性指數） | E |  |  , | 使用動態編程解決旅行推銷員問題 |
| 階乘時間 |  |  | 通過蠻力搜索解決旅行推銷員問題 | |
| 指數時間 | exptime |  |  , | 通過蠻力搜索解決矩陣鏈乘法 |
| 雙重指數時間 | 2-隔離 |  |  | 在Presburger算術中確定給定陳述的真相 |
恆定時間
據說算法是恆定的時間（也寫為
儘管名稱為“恆定時間”，但運行時間不必獨立於問題大小，但是運行時間的上限必須獨立於問題大小。例如，任務“如有必要，交換A和B的值，以便
對數時間
據說算法需要對數時間
在二進制樹上或使用二進制搜索時，通常會發現服用對數時間的算法。
一個
對數時間的一個示例是通過字典搜索給出的。考慮一個包含n條條目的字典d ，按字母順序排序。我們認為， 
聚集體時間
據說算法可以在Polyogarithmic的時間內運行
例如，矩陣鏈排序可以在平行的隨機訪問機上以各種趨勢時間求解，並且可以在圖中以完全動態的方式確定圖形是平面的
亞線性時間
據說一種算法在次線性時間內運行（通常是拼寫的時間） 
特定的術語sublinear時間算法通常是指隨機算法，這些算法對其輸入的一小部分進行採樣，並有效地處理它們以大致推斷整個實例的屬性。這種類型的均方根時間算法與屬性測試和統計數據密切相關。
算法可以在sublrinear時間內運行的其他設置包括：
- 具有線性或更高總工作的並行算法（允許它們讀取整個輸入），但次線性深度。
- 保證對輸入結構的假設的算法。一個重要的例子是對數據結構的操作，例如在排序的數組中的二進制搜索。
- 在輸入中搜索本地結構的算法，例如在1D數組中找到局部最小值（可以在
使用二進制搜索變體的時間）。一個密切相關的概念是本地計算算法（LCA），該算法收到有關某些有效大輸出的本地信息的大量輸入和查詢。
線性時間
據說算法需要線性時間，或者
在算法必須順序讀取其整個輸入的情況下，線性時間是最佳的時間複雜性。因此，已經投入了許多研究，以發現表現出線性時間或至少幾乎線性時間的算法。這項研究包括軟件和硬件方法。有幾種硬件技術利用並行性來提供此功能。一個示例是內容 - 可調的內存。線性時間的概念用於匹配算法的字符串，例如Boyer-Moore String-Search算法和Ukkonen的算法。
準線性時間
據說算法在準線性時間內運行（也稱為log-lineAr時間），如果
在準線性時間內運行的算法包括：
- 現場合併排序，
- QuickSort ，
- heapsort ，
- 快速傅立葉變換，
- Monge陣列計算，
在許多情況下， 
比較類型至少需要
下季節時間
如果_ 
例如，簡單的，基於比較的排序算法是二次的（例如插入排序），但是可以發現更高級的算法是次級的（例如， shell sort ）。沒有通用類型在線性時間內運行，但是從二次變為次級的變化非常重要。
多項式時間
如果其運行時間在算法的輸入大小中，即對某些正常數k的t （ n ）= o （ n k ） ，則認為其運行時間的運行時間是多項式時間的多項式時間。確定性多項式算法存在的問題屬於P類P類，這是計算複雜性理論領域的核心。 Cobham的論文指出，多項式時間是“可拖動”，“可行”，“有效”或“快速”的代名詞。
多項式時間算法的一些示例：
- 選擇排序排序算法在n個整數上執行
一個常數a的操作。因此它及時運行
- 所有基本的算術操作（加法，減法，乘法，除法和比較）都可以在多項式時間內完成。
- 圖中的最大匹配可以在多項式時間內找到。
強烈而弱的多項式時間
在某些情況下，尤其是在優化中，一個區分強度多項式時間和弱多項式時間算法。這兩個概念僅在算法的輸入由整數組成時才相關。
在計算的算術模型中定義了強烈的多項式時間。在此計算模型中，無論操作數的尺寸如何，基本的算術操作（加法，減法，乘法，除法和比較）都要執行單位時間步驟。如果以下方式，該算法在強烈的多項式時間內運行：
- 計算算術模型中的操作數量是在輸入實例中的整數中的多項式界定的。和
- 該算法使用的空間由輸入大小的多項式界定。
具有這兩種屬性的任何算法都可以通過通過合適的算法替換算術操作來轉換為多項式時間算法，以在圖靈機上執行算術操作。第二條件是嚴格必要的：鑑於整數
但是，對於第一個條件，有一些算法以多項式在二進制編碼輸入的長度上以多項式為界的許多圖靈機步中運行，但不接受許多算術操作，該操作是由多項式界定的，在輸入數量中。數字。用於計算兩個整數的最大常見除數的歐幾里得算法就是一個例子。給定兩個整數
在多項式時間內運行但不是強烈多項式的算法在弱多項式時間內運行。眾所周知的弱多項式時間算法的一個眾所周知的示例是線性編程是已知的，但尚不知道會接受強烈多項式時算法。弱的多項式時間不應與偽多項式時間混淆，這取決於問題中值的大小而不是長度，而不是真正的多項式時間。
複雜性類
多項式時間的概念導致計算複雜性理論中的幾個複雜性類別。以下是使用多項式時間定義的一些重要類。
- 警：在多項式時間內可以在確定性的圖靈機上解決的決策問題的複雜性類別
- NP ：在多項式時間內可以在非確定性圖靈機上解決的決策問題的複雜性類別
- ZPP ：在多項式時間內概率的圖靈機上可以用零錯誤解決的決策問題的複雜性類別類別
- RP ：在多項式時間內概率的圖靈機上可以通過1個方向誤差解決的決策問題的複雜性類別。
- BPP ：在多項式時間內概率的圖靈機上可以通過2個方向誤差解決的決策問題的複雜性類別
- BQP ：在多項式時間內在量子圖靈機上使用2個方向誤差解決的決策問題的複雜性類別
P是確定性機器上最小的時間複雜性類別，在機器模型變化方面非常健壯。 （例如，從單磁帶圖靈機更改到多錄像機可以導致二次加速，但是在一種模型下以多項式時間運行的任何算法也可以與另一個模型一起運行。）任何給定的抽像機器都會如此。具有與可以在該機器上多項式時間解決的問題相對應的複雜性類。
超級物質時間
如果t （ n ）不受任何多項式界限，則將算法定義為需要超級物質時間。使用Little Omega符號，是所有常數C的ω （ n C ）時間，其中N是輸入參數，通常是輸入中的位數。
例如，在大小n的輸入上以2 n個步驟運行的算法需要超級分類時間（更具體地說，更具體地說是指數時間）。
使用指數資源的算法顯然是超級單位的，但是某些算法僅是非常弱的超多種單位。例如， adleman – Pomerance- umumly Priminality測試在n位輸入上進行n o （log log n ）時間；對於足夠大的n ，它的生長速度比任何多項式的速度都快，但是在不能以較小程度的多項式支配它之前，輸入尺寸必須變得不切實際。
需要超級物質時間的算法在於複雜性類別以外。 Cobham的論文認為，這些算法是不切實際的，在許多情況下都是。由於未解決P與NP問題，因此尚不清楚NP完整問題是否需要超級物質時間。
準多項式時間
準多項式時間算法是算法的運行時間表現出準多項式生長，這是一種可能比多項式時間慢的行為，但速度明顯比指數時間快得多。準多項式時間算法的最糟糕的情況是
我們知道有一些問題，我們知道準多項式時間算法，但是尚無多項式時間算法。這些問題以近似算法出現。一個著名的例子是定向的施泰納樹問題，其中有一個準多項式時間近似算法達到了一個近似因素
準多項式時間解決方案的其他計算問題，但沒有已知的多項式時間解決方案包括種植的集團問題，在該問題中，目標是在集團和隨機圖的結合中找到一個大集團。儘管可以解決準真，但已經猜想種植的集團問題沒有多項式時間解決方案。這個種植的集團猜想已被用作計算硬度假設，以證明計算遊戲理論，屬性測試和機器學習中其他幾個問題的難度。
複雜性類別QP包括所有具有準多項式時間算法的問題。它可以按以下方式定義DTIME 。
與NP完整問題有關
在復雜性理論中，未解決的P與NP問題詢問NP中的所有問題是否具有多項式時間算法。 NP完整問題（例如3SAT等）的所有最著名的算法花費指數時間。實際上，它是針對許多自然的NP完整問題的猜想，它們沒有亞指數時間算法。在這裡，“亞指數時間”表示為以下所示的第二個定義。 （另一方面，鄰接矩陣以自然方式表示的許多圖形問題可以在次指數時間中解決，僅僅是因為輸入的大小是頂點數量的平方。）此猜想（對於K-SAT問題）是稱為指數時間假設。由於猜想NP完整問題沒有準多項式時間算法，因此某些不Xi異能性導致近似算法的領域導致假設NP - 完整問題沒有quasi-PolyNomial ialial時間算法。例如，請參閱設置蓋問題的已知無XIBIBIBIBITISION結果。
亞指數時間
術語次指數時間用於表達某些算法的運行時間可能比任何多項式的生長速度快，但仍然明顯小於指數。從這個意義上講，具有次指數時間算法的問題比僅具有指數算法的問題更容易拖拉。通常不同意“亞指數”的確切定義，但是最廣泛使用的兩個。
第一個定義
如果可以在對數小於任何給定多項式的跑步時間中求解，據說可以解決問題。更確切地說，如果每個ε > 0都存在一個算法，該算法解決了時間o （ 2nε ） ，則問題是在亞指數的時間內。所有此類問題的集合是複雜性類SubExp ，可以按以下方式定義DTIME 。
從ε不屬於輸入的一部分，每個ε的概念在ε方面是不均勻的，每個ε可能具有其自己的問題算法。
第二定義
一些作者將次指定時間定義為運行時間
是否允許算法在實例的大小，頂點數量或邊數的大小上為子指數，這有很大的不同。在參數化的複雜性中，通過考慮對顯式就可以顯式
更確切地說，替代是所有參數化問題的類別
指數時間假設
指數時間假設（ ETH ）是3SAT ，即布爾公式以相結合的正態形式與每個條款最多三個文字和n個變量，無法在時間2 o （ n ）中解決。更確切地說，假設是存在一些絕對常數C > 0 ，因此任何確定性圖靈機無法在時間2 CN中確定3SAT。通過表示條款的數量，ETH等同於以下假設：對於任何整數k≥3 ，時間2 O（ m ）無法在時間2 o （m）中求解。指數時間假設意味著p≠np 。
指數時間
如果t （ n ）由2個poly（ n ）界限，其中poly（poly（ n ）在n中是多項式的，則算法是指數時間。更正式的是，如果對於某些常數k ， t （ n ）由o （2 n k ）界定，則算法是指數時間。確定性圖靈機上接受指數時間算法的問題形成了稱為EXP的複雜性類別。
有時，指數時間用於指帶有t （ n ）= 2 O （ n ）的算法，其中指數最多是n的線性函數。這引起了複雜性e 。
階乘時間
如果t（n）受階乘函數n的上限，則據說算法是階乘時間！ 。階乘時間是指數時間的子集（EXP），因為
Bogosort是在階乘時間運行的算法的一個示例，這是一種基於反複試驗和錯誤的效率低下的分類算法。 Bogosort通過反復將列表列出直到被分類為止，將N項列表列出。在平均情況下，每個通過Bogosort算法將檢查N ！ n項的訂購。如果項目不同，則僅分類一個這樣的訂單。博哥特與無限的猴子定理分享了遺產。
雙重指數時間
如果t （ n ）由2 2 poly（ n ）界限，其中poly（poly（ n ）在n中是多項式的，則算法是雙重指數時間。這種算法屬於2類複雜性。
眾所周知的雙重指數時間算法包括：