運算複雜度理論
From Wikipedia, the free encyclopedia
運算複雜度理論(英文:computational complexity theory,CCT)係運算理論嘅一個子領域,集中於研究啲(最少理論上)解到嘅運算問題有幾撈絞-即係想分析如果要實際噉用電腦計呢啲問題嘅答案,要消耗幾多資源,當中資源包括咗時間同空間(空間指記憶體)呀噉[1][2]。
對運算複雜度嘅研究係電腦科技上嘅重要一環:簡單講,電腦本質上就係以極快速度計大量數嘅機械;但事實表明,有好多運算問題都係理論上解決到、但實際計起上嚟就要用好似宇宙年齡咁耐嘅時間;例如係好出名嘅旅行商問題噉,想像而家地圖上面有 咁多點,而個人想段演算法 output 出一條線,條線要達到[3][4]
- 行勻嗮咁多點、
- 每點淨係經過一次、兼且
- 起點同終點係同一點
三樣嘢(睇附圖);原則上,條問題係有可能解決嘅-分析者可以索性用最夾硬嚟嗰種方法,將啲可能路線冚唪唥逐條逐條睇一次,最後畀出最短嗰條路線做 output;但如果用噉嘅方法解,部電腦就要做 [註 1]咁多吓運算,而 數值稍為大少少, 已經會變成天文數字[3]。
運算複雜度相關知識,响好多實用工作上都有用,例如軟件工程噉,就成日會想做最佳化,將啲程式嘅源碼寫到「行起上嚟冇咁嘥時間同記憶體」噉嘅樣;所以軟件工程師就會參考運算複雜度知識,想要啲源碼要點寫,先可以令運算複雜度有咁低得咁低[5];比較學術性質嘅電腦科學工作者,仲有對運算複雜度作出數學性質嘅研究,想搵方法做到(例如)更有效率噉解運算問題。