无码精品人妻一区二区三区漫画,国产三级久久久精品麻豆三级,ww成人,成人毛片A片免费看,VA毛片,大鸡巴在线视频,永久免费污网站,麻豆成人在线视频

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

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

本詞條由集智俱樂部眾包生產(chǎn)，難免存在紕漏和問題，歡迎大家留言反饋或者前往對(duì)應(yīng)的百科詞條頁面進(jìn)行修改，一經(jīng)修改，可以獲得對(duì)應(yīng)的積分獎(jiǎng)勵(lì)！

一、資源

二、復(fù)雜度：輸入規(guī)模的函數(shù)

三、漸近復(fù)雜度

四、計(jì)算模型

五、問題復(fù)雜度（下限）

六、在算法設(shè)計(jì)中的應(yīng)用

七、編者推薦

八、百科項(xiàng)目志愿者招募

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

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

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

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

資源

時(shí)間

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

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

空間

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

其他

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

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

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

復(fù)雜度：輸入規(guī)模的函數(shù)

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

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

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

漸近復(fù)雜度

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

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

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

計(jì)算模型

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

確定性模型

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

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

非確定性計(jì)算

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

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

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

并行和分布式計(jì)算

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

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

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

量子計(jì)算

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

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

問題復(fù)雜度(下限)

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

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

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

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

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

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

在算法設(shè)計(jì)中的應(yīng)用

評(píng)估算法的復(fù)雜度是算法設(shè)計(jì) algorithm design的一個(gè)重要組成部分，因?yàn)檫@給出了一個(gè)算法關(guān)于預(yù)期性能的有用信息。

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

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