Can you summarize the following document?
        
  以下表格統整了一些常用的時間複雜度類別。表中,poly("x") = "x",也就是 "x" 的多項式。

  若對於一個演算法,formula_1的上界與輸入大小無關,則稱其具有常數時間,記作formula_2時間。一個例子是訪問陣列中的單個元素,因為訪問它只需要一條指令。但是,找到無序陣列中的最小元素則不是,因為這需要遍歷所有元素來找出最小值。這是一項線性時間的操作,或稱formula_3時間。但如果預先知道元素的數量並假設數量保持不變,則該操作也可被稱為具有常數時間。  雖然被稱為「常數時間」,執行時間本身不須與問題規模無關,但它的上界必須是與問題規模無關的確定值。舉例,「如果a > b則交換a、b的值」這項操作,儘管具體時間會取決於條件「a > b」是否滿足,但它依然是常數時間,因為存在一個常量t使得所需時間總不超過t。  以下是一個常數時間的程式碼片段:  如果formula_4,其中formula_5是一個常數,這記法等價於標準記法formula_6。

  若演算法的"T"("n") = O(log "n"),則稱其具有對數時間。計算機使用二進位制的記數系統,對數常常以2為底(即log "n",有時寫作lg "n")。然而,由對數的換底公式,log "n"和log "n"只有一個常數因子不同,這個因子在大O記法中被丟棄。因此記作O(log "n"),而不論對數的底是多少,是對數時間演算法的標準記法。  常見的具有對數時間的演算法有二叉樹的相關操作和二分搜尋。  對數時間的演算法是非常有效的,因為每增加一個輸入,其所需要的額外計算時間會變小。  遞迴地將字串砍半並且輸出是這個類別函式的一個簡單例子。它需要O(log n)的時間因為每次輸出之前我們都將字串砍半。 這意味著,如果我們想增加輸出的次數,我們需要將字串長度加倍。 // 遞迴輸出一個字串的右半部分 var right = function(str)

  對於某個常數"k",若演算法的"T"("n") = O((log "n")),則稱其具有冪對數時間。例如,矩陣鏈排序可以通過一個PRAM模型.被在冪對數時間內解決。

  對於一個演算法,若其符合"T"("n") = o("n"),則其時間複雜度為次線性時間(sub-linear time或sublinear time)。實際上除了符合以上定義的演算法,其他一些演算法也擁有次線性時間的時間複雜度。例如有O("n") 葛羅佛演算法演算法。  常見的非合次線性時間演算法都採用了諸如平行處理(就像NC matrix行列式計算那樣)、量子演算法(如同葛羅佛搜尋那樣),又或者選擇性地對有保證的輸入結構作出假設(如冪對數時間的二分搜尋)。不過,一些情況,例如在頭 log(n) 位元中每個字串有一個位元作為索引的字串組就可能依賴於輸入的每個位元,但又符合次線性時間的條件。  「次線性時間演算法」通常指那些不符合前一段的描述的演算法。它們通常執行於傳統電腦架構系列並且不容許任何對輸入的事先假設。但是它們可以是隨機化演算法,而且必須是真隨機演算法除了特殊情況。

  如果一個演算法的時間複雜度為O("n"),則稱這個演算法具有線性時間,或O("n")時間。非正式地說,這意味著對於足夠大的輸入,執行時間增加的大小與輸入成線性關係。例如,一個計算列表所有元素的和的程式,需要的時間與列表的長度成正比。這個描述是稍微不準確的,因為執行時間可能顯著偏離一個精確的比例,尤其是對於較小的n。

  若一個演算法時間複雜度T(n) = O(nlog n),則稱這個演算法具有線性對數時間。因此,從其表示式我們也可以看到,線性對數時間增長得比線性時間要快,但是對於任何含有n,且n的冪指數大於1的多項式時間來說,線性對數時間卻增長得慢。

  

  從多項式時間的概念出發,在計算複雜度理論中可以得到一些複雜度類。以下是一些重要的例子。  在機器模型可變的情況下,P在確定性機器上是最小的時間複雜度類。例如,將單帶圖靈機換成多帶圖靈機可以使演算法執行速度以二次階提升,但所有具有多項式時間的演算法依然會以多項式時間執行。一種特定的抽象機器會有自己特定的複雜度類分類。

  如果一個演算法的時間 "T"("n") 沒有任何多項式上界,則稱這個演算法具有超越多項式(superpolynomial)時間。在這種情況下,對於所有常數 "c" 我們都有 "T"("n") = ω("n"),其中 "n" 是輸入引數,通常是輸入的資料量(位元數)。指數時間顯然屬於超越多項式時間,但是有些演算法僅僅是很弱的超越多項式演算法。例如,對於 "n" 位元的輸入需要執行 "n" 時間;對於足夠大的 "n",這時間比任何多項式都快;但是輸入要大得不切實際,時間才能真正超過低階的多項式。

  準多項式時間演算法是運算慢於多項式時間的演算法,但不會像指數時間那麼慢。對一些固定的 formula_7,準多項式時間演算法的最壞情況執行時間是 formula_8。如果準多項式時間演算法定義中的常數“c”等於1,則得到多項式時間演算法;如果小於1,則得到一個次線性時間演算法。

  術語次指數時間用於表示某些演算法的運算時間可能比任何多項式增長得快,但仍明顯小於指數。在這種狀況下,具有次指數時間演算法的問題比那些僅具有指數演算法的問題更容易處理。“次指數”的確切定義並沒有得到普遍的認同,我們列出了以下兩個最廣泛使用的。

  如果一個問題解決的運算時間的對數值比任何多項式增長得慢,則可以稱其為次指數時間。更準確地說,如果對於每個 ε> 0,存在一個能於時間 O(2) 內解決問題的演算法,則該問題為次指數時間。所有這些問題的集合是複雜性SUBEXP,可以按照 DTIME 的方式定義如下。

  一些作者將次指數時間定義為 2 的運算時間。該定義允許比次指數時間的第一個定義更多的運算時間。這種次指數時間演算法的一個例子,是用於整數因式分解的最著名古典演算法——普通數域篩選法,其運算時間約為 formula_10,其中輸入的長度為 "n"。另一個例子是圖形同構問題的最著名演算法,其運算時間為 formula_11。

  若"T"("n") 是以 2為上界,其中 poly("n") 是 "n" 的多項式,則演算法被稱為指數時間。更正規的講法是:若 "T"("n") 對某些常數 "k"是由 O(2) 所界定,則演算法被稱為指數時間。在確定性圖靈機上認定為指數時間演算法的問題,形成稱為EXP的複雜性級別。  有時侯,指數時間用來指稱具有 "T"("n") = 2 的演算法,其中指數最多為 "n" 的線性函式。這引起複雜性等級 E。

  若 "T"("n") 是以 2 為上界,其中 poly("n") 是 "n" 的多項式,則演算法被稱為雙重指數時間。這種演算法屬於複雜性等級 2-EXPTIME。  眾所周知的雙重指數時間演算法包括:
在電腦科學中,演算法的時間複雜度(Time complexity)是一個函式,它定性描述該演算法的執行時間。這是一個代表演算法輸入值的字串的長度的函式。時間複雜度常用大O符號表述,不包括這個函式的低階項和首項係數。使用這種方式時,時間複雜度可被稱為是漸近的,亦即考察輸入值大小趨近無窮時的情況。例如,如果一個演算法對於任何大小為 "n" (必須比 "n" 大)的輸入,它至多需要 的時間執行完畢,那麼它的漸近時間複雜度是 O("n")。