在計算複雜性理論中，線性加速定理指時間複雜性可以任意地線性加速，即如果一個函式有時間的算法，則對任意小常數，必然存在時間的算法來計算；即對時間複雜性類的帶數目的減少。空間複雜性也可以類似任意地線性加速。
基本介紹
- 中文名：線性加速定理
- 外文名：linear speedup theorem
- 領域：計算機科學
- 定義：算法存在時間可解
- 有關術語：計算複雜性
- 方面：時間和空間複雜性
簡介,計算複雜性理論,方法,空間複雜度與時間複雜度,
簡介
圖靈機的線性加速定理是指：給定任意實數 c > 0 ，如果有任意圖靈機在 f(n) 時間內可以解決一個問題 L 則一定存在另一個圖靈機可以在 cf(n) + n + 2 的時間內解決這個問題 L。線性加速定理主要通過程式進行並行計算來實現和對問題進行算法最佳化。
這裡提供一個對於 c = 1/2 時的簡要的證明思路。假設一個包含有 k 條帶和 s 個狀態的圖靈機 M 可以在 f(n) 的時間內解決這個問題，構造一個新的圖靈機 M' 包含 k3 條帶，每一個符號表示一個 M 中連續的三個符號的一個區塊，即 M' 的帶上的符號是 M 上的符號的壓縮表示—— M' 的第 i 格上的符號表示 M 的第 2i-1 格、第 2i 格和第 2i+1 格的一個區塊上的符號（注意：這些區塊之間是交疊的）。在一個計算步驟中，M' 模擬 M 的計算步驟直到 M 的讀寫頭離開 M' 當前讀寫頭所表示的對應區塊到左側或右側的下一格（這一模擬可以在一步中完成，因為 M 在不離開 M' 中對應區塊或重複一個狀態的情況下最多有 3sk3 種狀態）。在這一模擬過程中， M 有可能接受（解決此問題），對應的 M' 也會接受（解決此問題）；或者 M 會一直循環下去，對應的 M' 會什麼也不做（或也對應的一直循環下去）。
最後一點需要注意的地方是：由於區塊可以交疊，因此這些區塊可能會在交疊出包含不連續的字元。在這種情況下，最接近當前讀寫頭位置的區塊才是正確的。當發生從一個區塊到另一個區塊的轉換時，圖靈機的狀態被用來暫時記錄開始區塊的那些交疊的符號，直到其可以被複製到目的區塊的對應位置。
這一構造需要 M' 的每一步計算要對應 M 的至少兩步計算。因此 M' 在最初的花費線性步驟的將輸入帶轉換為壓縮表示的步驟之後，最多還需要不會超過 f(n)/2 步。
這一證明可以被很容易的推廣到所有的 c > 0 的情況，通過讓每個區塊使用更多相鄰的符號來實現。一種叫做“帶壓縮定理”的相似技術可以用來在圖靈機所需的空間上去掉常因數。
計算複雜性理論
計算複雜性理論是計算機科學理論的一個重要組成部分，當代幾乎所有重要的科學問題都與計算複雜性有關，如人工智慧問題，認識極限問題等，這些問題都是科學前沿的一些重要但未解決的問題。用數學方法研究各類問題的計算複雜性的學科。它研究各種可計算問題在計算過程中資源(如時間、空間等)的耗費情況，以及在不同計算模型下，使用不同類型資源和不同數量的資源時，各類問題複雜性的本質特性和相互關係。
它對計算中所需的各種資源(計算時間、存儲空間等)的耗費作定量的分析，並研究各類問題之間在計算複雜程度上的相互關係和基本性質，是算法分析的理論基礎。在計算一類問題時，資源耗費的多少與被計算問題本身的大小有關，它是問題大小的函式，稱為問題對該資源需求的複雜度。計算複雜性理論研究的主要內容包括對複雜度函式增長的階進行分析，探討它們對於不同的計算模型在一定意義下的無關性，根據複雜度的階對被計算問題分類，研究各種不同資源耗費之間的關係，對一些基本問題的資源耗費情況的上、下界作估計等。
方法
並行計算或稱平行計算是相對於串列計算來說的。它是一種一次可執行多個指令的算法，目的是提高計算速度，及通過擴大問題求解規模，解決大型而複雜的計算問題。所謂並行計算可分為時間上的並行和空間上的並行。 時間上的並行就是指流水線技術，而空間上的並行則是指用多個處理器並發的執行計算。並行計算系統既可以是專門設計的、含有多個處理器的超級計算機，也可以是以某種方式互連的若干台的獨立計算機構成的集群。通過並行計算集群完成數據的處理，再將處理的結果返回給用戶。為利用並行計算，通常計算問題表現為以下特徵：
（1）將工作分離成離散部分，有助於同時解決；
（2）隨時並及時地執行多個程式指令；
（3）多計算資源下解決問題的耗時要少於單個計算資源下的耗時。
算法最佳化是指對算法的有關性能進行最佳化，如時間複雜度、空間複雜度、正確性、健壯性。大數據時代到來，算法要處理數據的數量級也越來越大以及處理問題的場景千變萬化。為了增強算法的處理問題的能力，對算法進行最佳化是必不可少的。算法最佳化一般是對算法結構和收斂性進行最佳化，算法結構最佳化簡單來說對需要處理的問題，設計新的算法。算法最佳化目的是為了在儘可能的小的時間和空間代價下尋找問題的最優解。
空間複雜度與時間複雜度
空間複雜度
空間複雜度S(n)定義為該算法所耗費的存儲空間，它也是問題規模n的函式。漸近空間複雜度也常常簡稱為空間複雜度。空間複雜度(SpaceComplexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間，算法的輸入輸出數據所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面。算法的輸入輸出數據所占用的存儲空間是由要解決的問題決定的，是通過參數表由調用函式傳遞而來的，它不隨本算法的不同而改變。存儲算法本身所占用的存儲空間與算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的算法。算法在運行過程中臨時占用的存儲空間隨算法的不同而異，有的算法只需要占用少量的臨時工作單元，而且不隨問題規模的大小而改變，我們稱這種算法是“就地\"進行的，是節省存儲的算法，有的算法需要占用的臨時工作單元數與解決問題的規模n有關，它隨著n的增大而增大，當n較大時，將占用較多的存儲單元，例如快速排序和歸併排序算法就屬於這種情況。
時間複雜度
在計算機科學中，算法的時間複雜度是一個函式，它定性描述該算法的運行時間。這是一個代表算法輸入值的字元串的長度的函式。時間複雜度常用大O符號表述，不包括這個函式的低階項和首項係數。使用這種方式時，時間複雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況。為了計算時間複雜度，我們通常會估計算法的操作單元數量，每個單元運行的時間都是相同的。因此，總運行時間和算法的操作單元數量最多相差一個常量係數。
相同大小的不同輸入值仍可能造成算法的運行時間不同，因此我們通常使用算法的最壞情況複雜度，記為 T(n) ，定義為任何大小的輸入 n 所需的最大運行時間。另一種較少使用的方法是平均情況複雜度，通常有特別指定才會使用。時間複雜度可以用函式 T(n) 的自然特性加以分類，舉例來說，有著 T(n) = O(n) 的算法被稱作“線性時間算法”；而 T(n) = O(Mn) 和 Mn= O(T(n)) ，其中 M ≥ n > 1 的算法被稱作“指數時間算法”。
