From Wikipedia, the free encyclopedia
運算複雜度理論(英文:computational complexity theory,CCT)係運算理論嘅一個子領域,集中於研究啲(最少理論上)解到嘅運算問題有幾撈絞-即係想分析如果要實際噉用電腦計呢啲問題嘅答案,要消耗幾多資源,當中資源包括咗時間同空間(空間指記憶體)呀噉[1][2]。
對運算複雜度嘅研究係電腦科技上嘅重要一環:簡單講,電腦本質上就係以極快速度計大量數嘅機械;但事實表明,有好多運算問題都係理論上解決到、但實際計起上嚟就要用好似宇宙年齡咁耐嘅時間;例如係好出名嘅旅行商問題噉,想像而家地圖上面有 咁多點,而個人想段演算法 output 出一條線,條線要達到[3][4]
三樣嘢(睇附圖);原則上,條問題係有可能解決嘅-分析者可以索性用最夾硬嚟嗰種方法,將啲可能路線冚唪唥逐條逐條睇一次,最後畀出最短嗰條路線做 output;但如果用噉嘅方法解,部電腦就要做 [註 1]咁多吓運算,而 數值稍為大少少, 已經會變成天文數字[3]。
運算複雜度相關知識,响好多實用工作上都有用,例如軟件工程噉,就成日會想做最佳化,將啲程式嘅源碼寫到「行起上嚟冇咁嘥時間同記憶體」噉嘅樣;所以軟件工程師就會參考運算複雜度知識,想要啲源碼要點寫,先可以令運算複雜度有咁低得咁低[5];比較學術性質嘅電腦科學工作者,仲有對運算複雜度作出數學性質嘅研究,想搵方法做到(例如)更有效率噉解運算問題。
定義上,CCT 研究嘅係運算複雜度:CCT 屬運算理論嘅子領域,起源自 1960 年代中[2];運算理論研究運算嘅數學特性,而 CCT 係呢種研究嘅一部份,旨在想[6]
「 | 」 |
舉個具體例子,
想像家陣研究者想寫返個程式,教電腦自動噉計
喺最壞情況下,用呢種夾硬嚟嘅做法解條問題,起碼要將步驟 1 至 3 做 ( 當中數值細啲嗰個)次咁多。喺現實世界,電腦要行演算法啲步驟,就最少會到兩種資源
CCT 想做嘅,就係攞「解決運算問題嘅演算法」做 input,畀若干個數值做 output,個 output 表示「段演算法消耗嘅資源量有幾多」(運算複雜度),當中以下呢兩種運算複雜度零舍受重視[1][9]:
CCT 嘅分析喺應用上好重要:例如想像有條問題,可運算性理論[e 3]嘅分析顯示佢係有可能用電腦解決嘅,但打後嘅分析發現,解決呢個問題要用嗰段演算法,就算用最先進嘅電腦行都要用成 100 年先行得完,噉嘅話呢條問題喺實際應用上根本冇得有效率噉解決;而且 CCT 仲能夠幫手判斷啲演算法「有幾好」-想像又有條問題,可以攞多隻唔同嘅演算法解決,而 CCT 就夠同每隻演算法畀啲數值出嚟,等電腦科學同軟件工程工作者有得客觀噉比較「邊隻演算法比較好」(正常嚟講,假設解問題嘅功效一樣,嘥嘅資源嘅量係愈少愈好)。因為噉,CCT 畀好多資訊科技工作者視為佢哋嗰行必備嘅知識[1]。
好多 IT 應用嘅工作,都涉及分析手上嘅演算法「有幾複雜」,例如家陣有班電腦科學家想提出一隻新嘅演算法,佢哋可以做嘅,就係攞隻新演算法去解問題,跟住又攞舊有嗰啲演算法解,畀人睇到「隻新演算法嘅複雜度低過打前嗰啲演算法,但解問題嗰陣嘅效用依然係咁好」[10][11]。喺實際應用上,佢哋通常會將運算複雜度表達做 input 嘅大細嘅函數,即係[1]:1.1.3
「 | 」 |
大 O 符號[e 4]嘅做法就係建基於上面條原則嘅。喺大 O 符號之下,一隻演算法嘅時間複雜度同空間複雜度通常寫成類似噉嘅樣:
當中 係個 input 嘅大細(例如如果個輸入係個數字, 會係佢有幾多個位), 反映隻演算法要行嘅步嘅數量隨 嘅變化,如果隻演算法要行嘅步數等如 ,噉即係話
... 如此類推。數學化啲噉講,就即係如果話 ,就可以搵到一個正嘅常數 ,令到[12]:321
假設每一步消耗嘅時間都一樣係 咁長,噉隻演算法行起上嚟要消耗嘅時間(時間複雜度)就可以輕易計埋出嚟。有咗上述嘅思考方式,就可以將啲演算法按複雜度分做[1][13]:
... 呀噉。上述呢啲「唔同款嘅複雜度」可以用下圖噉嘅方式想像:設 做「要行嘅步嘅數量最大係幾多」(),下圖裏面打戙條軸係 而打橫條軸就係 ;隨住 數值升 會跟住升,而「唔同款嘅複雜度」就可以想像成「唔同形狀嘅線」-
要衡量「一段演算法運算複雜度有幾高」,有好多種做法。
時間複雜度[e 1]係運算複雜度分析上最常用嘅複雜度指標,指緊「段演算法行嗮需要幾耐時間」,時間愈耐段演算法就愈算係複雜。喺實際應用上,一段演算法嘅時間複雜度唔會寫做「實際行段演算法需要幾耐時間」,而係會攞大 O 符號嚟表示[15][16]:Ch. 3。
首先,想像將段演算法寫做虛擬碼。設一條陣列 arr
,條陣列係段演算法嘅 input 而佢長度係 n
咁多,以下係段演算法嘅其中一橛仔[17]:
statement1;
statement2;
statement3;
好似以上嘅「就噉行三行陳述式」嘅碼,無論 n
係幾多都一樣係行一次,所以複雜度係 ,而好似以下噉嘅碼(睇埋 foreach 嘅概念):
同 arr 入面嘅每嚿數據,做
statement4;
上面嘅碼會將 statement4
行 n
咁多次,所以複雜度係 ... 如此類推[17]。
空間複雜度[e 2]係另一個運算複雜度分析上成日用到嘅指標,指「段演算法行嘅期間會霸幾多記憶體」。一般嚟講,任何要攞 input 嘅演算法行嗰陣,都實會霸一定量嘅記憶體-段演算法行嗰陣時,部電腦起碼實要搵啲記憶體記住個 input 嘅值;而除此之外,輔助空間[e 8]亦都會增加一段演算法嘅空間複雜度-輔助空間泛指 input 以外嘅數據霸走嘅記憶體,即係話
輔助空間裏面嘅數據,包括個程式會用到嘅非 input 常數同變數[16]:Ch. 3。
噉講即係話,要檢驗一段演算法嘅時間同空間複雜度,最基本上要䁽吓段演算法嘅碼,並且:
「 | 數吓每行碼『要行嘅次數』會點樣隨住 n 而變化(時間複雜度)同埋啲碼『用咗幾多 input 以外嘅常數同變數[註 6]』(空間複雜度)噉。 |
」 |
最好、最壞同平均情況複雜度係分析演算法複雜度嗰陣成日會講到嘅三個指標[18][19][20]:
舉例說明,用線性搜尋演算法做例子:試諗家陣要指定一個 input 數,再由一條 input 陣列度搵個數出嚟,如果陣列入面冇嗰個數,就顯示(例如)「搵唔到」,即係
要解呢條問題,線性搜尋係最簡單直接嗰種做法-即係將條陣列入面啲數逐個逐個攞嚟睇,搵到就畀嗰個數出嚟做 output,睇完嗮成條陣列都冇就畀「搵唔到」做 output。如果用線性搜尋解決條問題嘅話[19]:
喺廿一世紀初嘅應用上,最壞情況複雜度一般畀人視為重要資訊,分析演算法嗰時實會睇;相比之下,啲人比較少會留意平均同最好情況複雜度[18][註 8]。
複雜度類別[e 12]係運算複雜度分析上嘅一個重要概念。複雜度類別有好多款,一款複雜度類別會係一個集,包含一拃喺時間或者空間複雜度(睇返上面)上相似嘅運算問題。定義上,一款類別會講明三樣嘢[21]:1.1:
一款典型嘅複雜度類別(暫且嗌佢做 X),個定義望落會好似以下嘅句子噉[22]:
「 | X(呢個類別)包嗮所有可以由一部確定型圖靈機(模型)喺 咁多時間內(資源)解開嘅決定問題(問題)。 |
」 |
例如 P 類別可以算係最簡單嗰隻複雜度類別,包嗮所有可以由一部確定型圖靈機(模型)喺多項式時間[e 13]之內(資源)解開嘅決定問題(問題)-當中「多項式時間」意思係指段演算法「要行幾耐先解得到」嘅上限係[23]
咁多,當中 係某個正嘅常數。P 類型嘅問題可以算係「能夠有效噉解」嘅問題,例如「攞個數做 input,判斷個數係唔係質數」(質數判定)就係一條 P 型問題[23]。
除咗 P 之外,複雜度類別仲有好多種進階類型,例如 NP 噉:NP 包嗮所有可以由一部非確定型圖靈機(模型)喺多項式時間內(資源)解開嘅決定問題(問題);解 NP 型問題嘅演算法可以喺多項式時間內「判定佢搵到嗰個答案係咪正確」-簡化講,即係話呢啲問題「難以有效率噉樣解決,不過是但攞一個 output,可以相對容易噉檢驗個 output 係咪正確答案」[23][24]。
順帶一提,P 複雜度同 NP 複雜度嘅概念仲帶出咗所謂嘅 P-NP 問題。P-NP 問題係廿一世紀初嘅電腦科學上一條好出名嘅未解問題:條問題想問以下呢樣嘢[25][26]
「 | P 類別同 NP 類別係咪同一個集呢?P = NP? |
」 |
運算問題「係咪屬 P」呢點廣受關注:由上面大 O 符號幅圖睇得出,好似(例如)
等好多種唔屬 P 嘅極撈絞問題, 數值稍為大些少,已經會見到 數值變到極大,用電腦行都要計極耐先計得完-呢度「極耐」係講緊「就算假設部機能夠一路係噉行永遠唔壞,計條數要用嘅時間會去到宇宙年齡(想像由宇宙大爆炸至而家呢刻之間嘅時間)嗰種級數」,而同樣 值嘅 P 類別問題,就淨係要用(例如)幾個鐘頭嘅時間就行完。即係話喺實際應用上,呢啲唔屬 P 嘅極撈絞問題,除非係 好細嘅情況,例如 [註 9],否則根本解唔到。噉就表示「P = NP?」呢條問題嘅答案,對於好多運算問題「實用上有冇可能解決到」有極深遠嘅影響[25]。
到咗 2020 年代初,P-NP 問題依然係條未解之謎,而且仲有理論電腦科學相關嘅組織出數以百萬美金計嘅獎金,用嚟獎勵解到條問題嘅人[28]。
如果話一條運算問題屬於難解問題[e 14],意思係指嗰條問題「唔能夠有效率噉解決」。要留意嘅係,呢度講嘅「效率」唔係一般定義上嘅效率,而係[29][30]:p. 6
「 | 」 |
例如以下呢啲噉嘅時間複雜度都算係「能夠有效率噉解決」(唔係難解問題)
而以下呢啲時間複雜度就係「唔能夠有效率噉解決」(係難解問題)
簡單啲噉講,即係話一條難解問題可能理論上可以解決,甚至喺可運算性理論上證明咗係解到嘅,但電腦實際上冇可能做到喺夠短嘅時間內解條問題,即係例如如果
部機要出答案可以消耗極大量嘅時間,數量級都仲係會去到宇宙年齡嗰種層次-喺實際應用上根本解決唔到[31]。因為噉,要實際噉解難解問題嗰時,啲人正路唔會追求完美準確噉解決呢啲問題,而係會嘗試教部機「搵個有返咁上下理想嘅答案,然後收手」-詳情可以睇吓數學最佳化同逼近理論等嘅數學概念[32],亦可以睇吓著名人工智能程式 AlphaGo [33]。
Info:旅行商問題
旅行商問題[e 15]係一條好出名嘅難解問題。想像家陣有個 sell 士要去做推銷,佢攞住幅地圖,知自己要去勻香港、澳門、深圳、珠海、東莞、佛山、中山同廣州等多座喺珠江周圍嘅城市,然後佢自然想搵出一條最短可能路線,條路線要達到[3][4]
- 行勻嗮咁多座城市、
- 每座城市淨係經過一次、兼且
- 起點同終點係同一笪地方
呢三點。廣義化些少嘅話,旅行商問題可以當做任何
- Input:攞幅有若干粒節點嘅圖,
- Output:畀出一條最短可能嘅線,達致「去勻嗮啲節點、每粒節點淨係經過一次、起點同終點係同一點」。
呢條問題就噉望落好似好簡單,但事實表明佢係條難解問題:想像家陣用窮舉搜尋嚟解旅行商問題,將啲可能路線組合冚唪唥睇嗮佢-睇勻「香港-深圳-東莞-...」同「香港-深圳-珠海-...」... 如此類推等咁多個組合,噉做嘅時間複雜度會係
咁多,當中 係指節點嘅數量。呢個情況極冇效率(可以睇返上面大 O 符號相關嘅圖表),個 大些少已經會搞到部機做唔到「喺有限時間內出答案」;而且上面呢個情況只係最簡單嗰隻旅行商問題-如果要响現實世界解旅行商問題,部機仲起碼要考慮埋「每條路線成本都唔同」噉嘅問題,因為正常嚟講條條路嘅特性(長度同塞車嘅機率呀噉)都唔同[34]。自從廿世紀起,旅行商問題就吸引咗好多電腦科學同商學工作者嘅關注,例如一間企業會想計劃自己送貨路線嗰陣,就要面對好似旅行商問題噉嘅情況-送貨路線設計得唔好,會搞到燃料等嘅成本明顯上升[35]。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.