EITC/IS/CCTF 計算複雜性理論基礎

因為運行算法所需的資源量隨輸入的大小而變化，所以復雜度通常表示為函數 f(n)，其中 n 是輸入大小，f(n) 是最壞情況復雜度（所有大小為 n 的輸入所需的最大資源量）或平均案例複雜度（大小為 n 的所有輸入的資源量的平均值）。 在大小為 n 的輸入上所需的基本操作的數量通常表示為時間複雜度，其中基本操作被認為在特定計算機上花費恆定的時間，並且當在不同的機器上運行時僅以恆定因子變化。 算法對大小為 n 的輸入所需的內存量稱為空間複雜度。

時間是最常被考慮的資源。 當術語“複雜性”不帶限定詞使用時，通常是指時間的複雜性。

傳統的時間單位（秒、分鐘等）在復雜性理論中沒有採用，因為它們過於依賴所選的計算機和技術的進步。 例如，今天的計算機可以比 1960 年代的計算機更快地執行算法，然而，這是由於計算機硬件的技術突破，而不是算法的固有質量。 複雜性理論的目標是量化算法的內在時間需求，或算法對任何計算機施加的基本時間限制。 這是通過計算在計算過程中執行了多少基本操作來完成的。 這些過程通常被稱為步驟，因為它們被認為在特定機器上花費恆定的時間（即，它們不受輸入量的影響）。

另一個重要資源是執行演算法所需的電腦記憶體量。

另一個經常使用的資源是算術運算的數量。 在這種情況下，使用術語“算術複雜性”。 如果計算期間出現的數字的二進製表示的大小的上限已知，則時間複雜度通常是算術複雜度乘以常數因子的乘積。

計算過程中使用的整數的大小不受許多方法的限制，假設算術運算需要固定的時間是不現實的。 因此，時間複雜度（也稱為位複雜度）可能會明顯高於算術複雜度。 例如，對於標準技術（高斯消元法），計算 nn 個整數矩陣的行列式的算術難度是 O(n^3)。 由於在計算過程中係數的大小可能會呈指數增長，因此相同方法的位複雜度是 n 的指數。 如果將這些技術與多模運算結合使用，則位複雜度可以降低到 O(n^4)。

位複雜度在形式上是指運行算法所需的位操作數。 在大多數計算範例中，它等於時間複雜度直到一個常數因子。 計算機所需的機器字操作數與位複雜度成正比。 對於現實的計算模型，時間複雜度和比特複雜度因此是相同的。

在排序和搜索中經常考慮的資源是條目比較的數量。 如果數據排列得當，這是時間複雜度的一個很好的指標。

在所有潛在輸入上，計算算法中的步驟數是不可能的。 因為輸入的複雜度隨其大小而增加，它通常表示為輸入大小 n（以位為單位）的函數，因此復雜度是 n 的函數。 然而，對於相同大小的輸入，算法的複雜性可能會有很大差異。 因此，經常使用各種複雜性函數。

最壞情況復雜度是所有大小為 n 的輸入的所有復雜度之和，而平均情況復雜度是所有大小為 n 的輸入的所有復雜度之和（這是有道理的，因為給定大小的可能輸入的數量是有限）。 當使用術語“複雜度”而沒有進一步定義時，會考慮最壞情況的時間複雜度。

眾所周知，最壞情況和平均情況的複雜性很難正確計算。此外，這些精確值幾乎沒有實際應用，因為機器或計算範式的任何變化都會稍微改變複雜性。此外，對於較小的 n 值，資源使用並不重要，因此對於較小的 n 而言，易於實現通常比低複雜性更有吸引力。

由於這些原因，大多數注意力都集中在高 n 的複雜性行為上，即當 n 接近無窮大時它的漸近行為。 因此，通常使用大 O 表示法來表示複雜性。

計算模型

計算模型的選擇（包括指定在單位時間內執行的基本操作）對於確定複雜性非常重要。當沒有具體描述計算範例時，這有時被稱為多帶圖靈機。

確定性計算模型是機器的後續狀態和要執行的操作完全由先前狀態定義的模型。 遞歸函數、λ演算和圖靈機是最早的確定性模型。 隨機存取機器（也稱為 RAM 機器）是模擬現實世界計算機的流行範例。

當計算模型未定義時，通常假定為多帶圖靈機。 在多磁帶圖靈機上，大多數算法的時間複雜度與 RAM 機器上的相同，儘管可能需要相當注意數據在內存中的存儲方式才能實現這種等效性。

可以在非確定性計算模型（例如非確定性圖靈機）中的某些計算步驟中做出各種選擇。 在復雜性理論中，同時考慮所有可行的選項，非確定性時間複雜度是始終做出最佳選擇所需的時間量。 換句話說，計算是在所需數量的（相同的）處理器上同時完成的，非確定性計算時間是第一個處理器完成計算所花費的時間。 這種並行性可以通過在運行專門的量子算法時使用疊加的糾纏態來用於量子計算，例如 Shor 的微小整數分解。

即使這樣的計算模型目前不可行，但它具有理論意義，特別是對於 P = NP 問題，該問題詢問使用“多項式時間”和“非確定性多項式時間”產生的複雜度類別是否為最小上界限是一樣的。 在確定性計算機上，模擬 NP 算法需要“指數時間”。 如果一項任務可以在非確定性系統上以多項式時間解決，則它屬於 NP 難度類。 如果一個問題在 NP 中並且並不比任何其他 NP 問題更容易，則稱它是 NP 完全的。 背包問題、旅行商問題和布爾可滿足性問題都是 NP 完全組合問題。 最著名的算法對所有這些問題都具有指數複雜性。 如果這些問題中的任何一個都可以在確定性機器上在多項式時間內解決，那麼所有 NP 問題也可以在多項式時間內解決，並且 P = NP 將成立。 截至 2017 年，人們普遍假設 P NP，這意味著 NP 問題的最壞情況從根本上難以解決，即在給定有趣的輸入長度的情況下，所花費的時間遠遠超過任何可行的時間跨度（數十年）。

並行和分佈式計算

並行和分佈式計算涉及在同時運行的多個處理器之間劃分處理。 各種模型之間的根本區別在於處理器之間發送數據的方法。 在並行計算中，處理器之間的數據傳輸通常非常快，而在分佈式計算中，處理器之間的數據傳輸是通過網絡完成的，因此速度要慢得多。

在 N 個處理器上的計算至少需要 N 個商在單個處理器上花費的時間。 實際上，由於某些子任務無法並行化，並且某些處理器可能需要等待另一個處理器的結果，因此永遠無法達到這種理論上的理想界限。

因此，關鍵的複雜性問題是開發算法，以使計算時間與處理器數量的乘積盡可能接近在單個處理器上執行相同計算所需的時間。

量子計算

量子計算機是具有基於量子力學的計算模型的計算機。 Church-Turing 論點適用於量子計算機，這意味著量子計算機可以解決的任何問題也可以由圖靈機解決。 然而，一些任務理論上可以使用量子計算機而不是時間複雜度顯著降低的經典計算機來解決。 目前，這只是理論上的，因為沒有人知道如何開發實用的量子計算機。

創建量子復雜性理論是為了研究量子計算機可以解決的不同類型的問題。 它用於後量子密碼學，這是創建能夠抵抗量子計算機攻擊的密碼協議的過程。

問題的複雜性（下限）

可能解決問題的算法的複雜性（包括未被發現的技術）的下確界就是問題的複雜性。 因此，問題的複雜性等於解決它的任何算法的複雜性。

因此，任何以大 O 表示法給出的複雜度都代表了算法和伴隨問題的複雜度。

另一方面，獲得問題複雜性的非平凡下限通常很困難，而且這樣做的策略很少。

為了解決大多數問題，必須讀取所有輸入數據，這需要與數據量成正比的時間。 結果，這些問題至少具有線性複雜度，或者，在大歐米茄符號中，複雜度為 Ω(n)。

一些問題，例如計算機代數和計算代數幾何中的問題，有非常大的解決方案。 因為必須寫入輸出，所以復雜性受輸出的最大大小的限制。

排序算法所需的比較次數具有 Ω(nlogn) 的非線性下限。 因此，最好的排序算法是最有效的，因為它們的複雜度是 O(nlogn)。 事實上有 n! 組織 n 個事物的方法導致了這個下限。 因為每次比較都會劃分這個 n 的集合！ 訂單分成兩部分，區分所有訂單所需的 N 比較次數必須是 2N > n!，根據斯特林公式，這意味著 O(nlogn)。

將一個問題簡化為另一個問題是獲得降低複雜性約束的常用策略。

算法開發

評估算法的複雜性是設計過程的一個重要元素，因為它提供了有關預期性能的有用信息。

一個常見的誤解是，由於摩爾定律預測現代計算機能力的指數增長，評估算法的複雜性將變得不那麼重要。 這是不正確的，因為增加的功率允許處理大量數據（大數據）。 例如，當按字母順序對數百個條目的列表進行排序時，任何算法都應該在不到一秒的時間內運行良好，例如一本書的參考書目。 另一方面，對於一百萬個條目（例如，一個大城市的電話號碼），需要 O(n2) 比較的基本算法必須執行一萬億次比較，以 10 的速度需要三個小時每秒百萬次比較。 另一方面，快速排序和合併排序只需要 nlogn 比較（前者的平均複雜度，後者的最壞情況復雜度）。 對於 n = 30,000,000，這會產生大約 1,000,000 次比較，如果每秒進行 3 萬次比較，這將只需要 10 秒。

因此，評估複雜性可以允許在實施之前消除許多低效的算法。 這也可以用於微調複雜的算法，而無需測試所有可能的變體。 對複雜性的研究允許通過確定複雜算法中最昂貴的步驟來集中精力提高實現的效率。