什么是計算復(fù)雜度？

“集智百科精選”是一個長期專欄，持續(xù)為大家推送復(fù)雜性科學相關(guān)的基本概念和資源信息。作為集智俱樂部的開源科學項目，集智百科希望打造復(fù)雜性科學領(lǐng)域最全面的百科全書，歡迎對復(fù)雜性科學感興趣、熱愛知識整理和分享的朋友加入！

本文是對集智百科中“計算復(fù)雜度”詞條的摘錄，參考資料及相關(guān)詞條請參閱百科詞條原文。

在計算機科學 computer science中，一個算法 algorithm的計算復(fù)雜度或簡單的復(fù)雜度就是運行這個算法所需要的資源量，特別是時間（CPU占用時間）和空間（內(nèi)存占用空間）需求。

由于運行一個算法所需的資源量通常隨輸入規(guī)模的大小而變化，因此復(fù)雜度通常用函數(shù) f(n)表示，其中n是輸入量的大小，f(n)是最壞情況復(fù)雜度 worst-case complexity(輸入大小為 n時所需的資源量的最大值) ，或是平均情況復(fù)雜度 average-case complexity(資源總量相對于n的所有占用的平均值)。時間復(fù)雜度 Time complexity通常表示為對一個輸入值長度所需基本操作（通常是加法操作或者乘法操作）的數(shù)量。我們假設(shè)基本操作在一臺計算機上只占用一個不變的時間量（比如1納秒），而在另一臺計算機上運行時，只根據(jù)一個常量因子進行改變（比如k*1納秒）。空間復(fù)雜度 space complexity通常表示為算法對一個輸入值長度所需的內(nèi)存量。

對一個有明確定義的算法的復(fù)雜度進行的研究叫做算法分析 analysis of algorithm，而對問題的復(fù)雜度研究叫做計算復(fù)雜度理論 computation complexity theory分析。舉個例子，怎樣把一串數(shù)字從小到大進行排序，是一個問題；而針對這一問題，我們有多種明確定義的算法，如選擇排序，歸并排序等。假設(shè)我們有n個數(shù)字，那么排序問題的復(fù)雜度就是nlogn，而選擇排序的復(fù)雜度是n^2，歸并排序的復(fù)雜度是6nlogn。

這兩個領(lǐng)域是高度相關(guān)的，因為算法的復(fù)雜度一直是該算法所求解問題復(fù)雜度的上限 upper bound。

時間

最常被考慮的資源是時間。當沒有明確說明時，“復(fù)雜度”通常意味著時間復(fù)雜度而非空間復(fù)雜度。

在復(fù)雜度理論中不使用通常的時間單位(秒、分等)，因為它們過于依賴于特定計算機的選擇和技術(shù)的演變。例如，今天的計算機執(zhí)行算法的速度明顯快于20世紀60年代的計算機; 然而，這不是算法的固有特征，而是計算機硬件技術(shù)進步的結(jié)果。復(fù)雜度理論旨在量化算法的內(nèi)在時間需求，也就是算法對任何計算機的基本時間約束。這是通過統(tǒng)計在計算過程中執(zhí)行的基本操作數(shù)量來實現(xiàn)的。這些基本操作假定在給定的機器上占用常量時間(即不受輸入大小的影響)，通常被稱為步驟。

空間

另一個重要的資源是運行算法所需的計算機內(nèi)存 computer memory大小。

其他

算術(shù)運算 arithmetic operations的數(shù)量是另一種常用的資源。在這種情況下，人們會談到算術(shù)復(fù)雜度。如果已知一個計算過程中出現(xiàn)的數(shù)的二進制表示 binary representation長度的上限 upper bound，時間復(fù)雜度通常是該算術(shù)復(fù)雜度乘以一個常數(shù)因子。

對于許多算法，在計算過程中使用的整數(shù)大小是沒有界限的，并且考慮算術(shù)運算占用一個常量時間是不現(xiàn)實的。因此，時間復(fù)雜度，在此上下文中通常稱為 位復(fù)雜度 bit complexity，可能遠遠大于算術(shù)復(fù)雜度。例如，根據(jù)通常的算法 高斯消去法 Gaussian elimination 計算一個n×n 整數(shù)矩陣行列式 的算術(shù)復(fù)雜度是O(n^3)。因為系數(shù)的大小可能在計算過程中呈指數(shù)增長，相同算法的位復(fù)雜度是指數(shù)級的。另一方面，如果這些算法與多模運算相結(jié)合，位復(fù)雜度可以降低到O~(n4)。

在排序 sorting和搜索 searching中，通常考慮的資源是需要做幾次比較大小。如果數(shù)據(jù)組織得當，這通常是一個很好的時間復(fù)雜度測量方法。

為了清晰起見，本節(jié)只考慮時間復(fù)雜度，不過所有內(nèi)容(稍加修改)也都適用于其他資源的復(fù)雜度。

計算一個算法對于所有可能輸入的所需要的步驟數(shù)是不可能的。由于復(fù)雜度通常隨著輸入的規(guī)模而增加，復(fù)雜度通常表示為輸入值 n 長度（以比特 bit為單位）的函數(shù)。因此，復(fù)雜度是一個關(guān)于 n 的函數(shù)。然而，對于同樣長度的不同輸入，算法的復(fù)雜度可能會大不相同。因此，有多種不同的復(fù)雜度函數(shù)被廣泛使用。

最壞情況復(fù)雜度 worst-case complexity是對所有輸入n長度中的最大復(fù)雜度，平均情況復(fù)雜度 average-case complexity是對所有輸入n長度中的平均復(fù)雜度。一般來說，如果使用“復(fù)雜度”一詞且不進行進一步說明 ，即考慮最壞情況時間復(fù)雜度。

通常很難精確計算最壞情況和平均情況復(fù)雜度。此外，由于計算機或計算模型的任何變化都會改變復(fù)雜度，精確的復(fù)雜度值沒多少實際意義。更多地，對于較小的n值，資源的使用并不是關(guān)鍵。因此對于小 n，人們通常更在乎一個算法的簡單性和易實現(xiàn)性，而非復(fù)雜度。

由于這些原因，人們通常把注意力集中在大n的復(fù)雜度上，即輸入規(guī)模趨于無窮大的漸近行為 asymptotic behavior上。因此，復(fù)雜度通常用大O符號 big O notation來表示。

例如，通常整數(shù)乘法 multiplication的復(fù)雜度是O(n^2)，這意味著存在一個常數(shù)Cu，使得兩個最多n位的整數(shù)乘法可以在小于Cun^2的時間內(nèi)完成。這個界限是尖銳的，因為最壞情況復(fù)雜度和平均情況復(fù)雜度是Ω(n^2)。意味著存在一個常數(shù)Cl，使得這些復(fù)雜度比Cln^2大。

復(fù)雜度的評估依賴于計算模型 model of computation的選擇，包括定義在一個時間單位內(nèi)完成的基本操作。當沒有明確指定時，默認使用的計算模型是多帶圖靈機 multitape Turing machine。

確定性模型

一個確定性模型 deterministic model 的計算是一種機器的后續(xù)狀態(tài)和要執(zhí)行的操作完全由前面的狀態(tài)決定的計算模型。歷史上，最早的確定性模型是遞歸函數(shù) recursive functions、 lambda演算 lambda calculus和圖靈機 Turing machines。隨機存取機器 Random access machine (也稱 RAM-machines)的模型也被廣泛使用，更接近真實的計算機 computer。

當計算模型沒有被指定時，通常假設(shè)它是一個多帶圖靈機 multitape Turing machine。對于大多數(shù)算法，在多帶圖靈機上的時間復(fù)雜度與在RAM-machines上的相同，盡管可能需要注意如何將數(shù)據(jù)存儲在內(nèi)存中，以確保這種等價性。

非確定性計算

在非確定性計算模型 non-deterministic model of computation中，例如不確定的圖靈機 non-deterministic Turing machine，在計算的某些步驟中可能會進行一些選擇。在復(fù)雜度理論中，非確定性時間復(fù)雜度即為，同時考慮所有可能的選擇且做出最佳選擇時所需的時間。換句話說，我們認為計算是多個（相同的）處理器上同時進行的，而不確定計算時間是第一個完成計算的處理器所花費的時間。這種并行性在一定程度上可以通過運行特定量子算法 quantum algorithm的疊加糾纏態(tài) entangled state來實現(xiàn)量子計算 quantum computing。例如小整數(shù)上的肖爾因式分解 Shor's factorization。

即使這樣的計算模型還不現(xiàn)實，它仍然具有重要的理論意義，主要涉及P = NP? 問題。如果一個問題可以在確定性圖靈機上以多項式時間 polynomial time求解，則該問題屬于 P 類問題。如果一個問題可以在非確定性機器上以多項式時間 polynomial time求解，則該問題屬于 NP 類問題。我們知道所有P類問題都屬于NP類問題，但是否所有NP類問題也屬于P類問題？亦即，是否P類問題和NP類問題是等價的？這就是所謂的 P=NP? 問題

如果一個問題屬于 NP 問題，且不比其他任何 NP 問題簡單，則稱該問題為 NP完全問題 NP-complete。許多組合 combinatorial問題，例如背包問題 Knapsack problem、旅行推銷員問題 travelling salesman problem和布爾可滿足性問題 Boolean satisfiability problem都是NP完全問題。對于所有這些問題，最著名的算法具有指數(shù)復(fù)雜度。如果這些問題中的任何一個都可以在確定性機器上在多項式時間內(nèi)求解，那就意味著所有 NP 問題都可以在多項式時間內(nèi)求解，我們立即可以得出結(jié)論：P = NP。一般認為P類問題和NP類問題是等價的，即所有NP類問題都有在確定性圖靈機上以多項式時間解決的方法。現(xiàn)在我們主要的猜想是，NP 問題的最壞情況本質(zhì)上是難以解決的，即P≠NP。

并行和分布式計算

并行處理器和分布式計算處理器由同時工作的多個處理器組成。不同模型之間的差異主要體現(xiàn)在處理器之間的信息傳輸方式上。通常情況下，在并行計算中處理器之間的數(shù)據(jù)傳輸非常快，而在分布式計算中，數(shù)據(jù)傳輸通過網(wǎng)絡(luò)完成，因此速度要慢得多。

在N個處理器上進行計算所需的時間至少是單個處理器所需時間的N的商。但實際上，這個理論上的最優(yōu)界限永遠不可能達到，由于有些子任務(wù)不能并行化，部分處理器不得不先等待另一個處理器的結(jié)果。

因此，主要的復(fù)雜度問題是如何設(shè)計算法，使得計算時間與處理器數(shù)量的乘積盡可能接近在單個處理器上進行同一計算所需的時間。

量子計算

量子計算機 quantum computer是一種基于量子力學 quantum mechanics的計算機。丘奇-圖靈理論 Church–Turing thesis適用于量子計算機，也就是說，任何可以由量子計算機解決的問題也可以由圖靈機解決。然而，有些問題理論上可以用量子計算機以極低的時間復(fù)雜度 time complexity解決，而用傳統(tǒng)圖靈機則無法解決。由于沒有人知道如何建造一臺高效的量子計算機，目前這純粹只是理論上可行的。

量子復(fù)雜度理論 Quantum complexity theory研究用量子計算機解決的問題的復(fù)雜度類。它主要用于后量子密碼學 post-quantum cryptography，包括設(shè)計能抵御量子計算機攻擊的安全協(xié)議 cryptographic protocol。

問題的復(fù)雜度是解決問題算法(包括未知算法)復(fù)雜度的下確界 infimum，即解決這個問題所需的最少時間。因此，問題的復(fù)雜度比任何解決該問題的算法的復(fù)雜度都要小。

用大O符號 big O notation表示的每一個復(fù)雜度都是算法的復(fù)雜度，也是相應(yīng)問題的復(fù)雜度。

另一方面，問題復(fù)雜度的非平凡（nontrivial）下界一般難以獲得，并且獲得這種下界的方法很少。

為了解決大多數(shù)問題，往往需要與數(shù)據(jù)大小成比例的時間來讀取所有輸入數(shù)據(jù)。因此，這些問題的復(fù)雜度至少是線性的 linear，使用大歐米茄符號 big omega notation，記為復(fù)雜度Ω(n)。

一些問題的解可能是非常大的，特別是計算機代數(shù) computer algebra和計算代數(shù)幾何 computational algebraic geometry。在這種情況下，復(fù)雜度以輸出的最大長度為下界，因此輸出必須被寫入。例如，如果解的個數(shù)是有限的，n個d次不確定多項式方程組 system of n polynomial equations of degree d in indeterminates 可能有多達d^n個復(fù)解(這是貝佐定理 Bézout's theorem)。由于這些解必須被寫入，所以這個問題的復(fù)雜度是Ω(d^n)。對于這個問題，已知一個復(fù)雜度為d^(O(n))的算法，因此可以認為是漸近擬最優(yōu)的。

獲得復(fù)雜度下限的標準方法包括將一個問題轉(zhuǎn)化為另一個問題。更準確地說，假設(shè)一個大小為n的問題A可以編碼成大小為f(n)的問題B，則問題A的復(fù)雜度為Ω(g(n))。不失一般性地，我們可以假設(shè)函數(shù)f隨著n的增加而增加，并且有一個反函數(shù) inverse function，那么問題B的復(fù)雜度就是Ω(g(h(n)))。這個方法可以用來證明，若P ≠ NP(一個未解決的猜想) ，對于每個正整數(shù)k，每個NP完全問題 NP-complete problem的復(fù)雜度都是Ω(n^k)。

評估算法的復(fù)雜度是算法設(shè)計 algorithm design的一個重要組成部分，因為這給出了一個算法關(guān)于預(yù)期性能的有用信息。

有一個常見的誤解，由于摩爾定律 Moore's law假定了現(xiàn)代計算機功率的指數(shù)增長 exponential growth，對算法復(fù)雜度的評估將變得不那么重要。這是錯誤的，因為這種功率增加同樣也會容使得處理較大的輸入數(shù)據(jù)（大數(shù)據(jù)）成為可能。例如，當一個人想要按字母順序?qū)?shù)百個條目的列表進行排序時，比如一本書的參考書目，任何算法都應(yīng)該在不到一秒的時間內(nèi)就能正常工作。另一方面，對于一個包含100萬個條目的列表(例如一個大城鎮(zhèn)的電話號碼) ，需要O(n^2)次比較的基本算法，須進行1萬億次比較運算，即以每秒1000萬次的速度進行比較需要大約3個小時。另一方面，快速排序和合并排序 只需要nlog2n次比較(前者為平均情況復(fù)雜度，后者為最壞情況復(fù)雜度)。這大約是3000萬次比較，以每秒1000萬次比較計算，只需要3秒鐘。

因此，對復(fù)雜度的評估允許在編程實現(xiàn)之前就消除許多低效率的算法。這也可用于在不用測試所有變量的情況下調(diào)優(yōu)復(fù)雜的算法。通過確定復(fù)雜算法中最復(fù)雜的步驟，對復(fù)雜度的研究還可以將重點放在這些步驟上，從而提高實現(xiàn)的效率。

本文來源：集智俱樂部，版權(quán)屬于原作者，僅用于學術(shù)分享

免責申明：本號聚焦相關(guān)技術(shù)分享，內(nèi)容觀點不代表本號立場，可追溯內(nèi)容均注明來源，發(fā)布文章若存在版權(quán)等問題，請留言聯(lián)系刪除，謝謝。

電子書<服務(wù)器基礎(chǔ)知識全解(終極版)>更新完畢，知識點深度講解，提供182頁完整版下載。

獲取方式：點擊“閱讀原文”即可查看PPT可編輯版本和PDF閱讀版本詳情。

溫馨提示：

請搜索“AI_Architect”或“掃碼”關(guān)注公眾號實時掌握深度技術(shù)分享，點擊“閱讀原文”獲取更多原創(chuàng)技術(shù)干貨。