【益智遊戲】：真假金幣問題_綠翠園_濁水溪畔的國中生部落格

	§網綠翠園站§ 　　濁水溪畔的國中生部落格

主題：【益智遊戲】：真假金幣問題

發表：濁水溪畔的國中生	2012-05-13 16:00:56	閱覽數：38238	(IP: )	T 3493	引　用

回應：濁水溪畔的國中生	2012-05-13 16:09:14	(IP: )	T 3493_R 3	引　用

為保障我弟弟未來的權益，照例貼一些蠻複雜的東東來模糊焦點……^+++++++++^

【轉貼節錄wiki】：計算複雜性理論（Computational complexity theory）是計算理論的一部分，研究計算問題時所需的資源，比如時間（要通過多少步才能解決問題）和空間（在解決問題時需要多少記憶體），以及如何盡可能的節省這些資源。其他資源亦可考慮，例如在並行計算中，需要多少並行處理器才能解決問題。

【時間複雜度】──是指電腦完成一個演算法所需要的時間，是衡量一個演算法優劣的重要參數。時間複雜度越小，說明該演算法效率越高，則該演算法越有價值。

【空間複雜度】──是指電腦完成一個演算法所需要佔用的存儲空間，一般是輸入參數的函數，它是演算法優劣的重要度量指標。一般來說，空間複雜度越小，演算法越好。我們假設有一個圖靈機來解決某一類語言的某一問題，設有X個字（word）屬於這個問題，把X放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數總和稱為空間。

複雜度理論和可計算性理論不同，可計算性理論的重心在於問題能否解決，不管需要多少資源。而複雜性理論作為計算理論的分支，某種程度上被認為和演算法理論是一種【矛】與【盾】的關係，即演算法理論專註於設計有效的演算法，而複雜性理論專註於理解為什麼對於某類問題，不存在有效的演算法。

在20世紀50年代，Trahtenbrot和Rabin的論文被認為是該領域最早的文獻。一般說來，被公認奠定計算複雜性領域基礎的是Hartmanis和Stearns的1960年代的論文On the computational complexity of algorithms。在這篇論文中，作者引入了時間複雜性類TIME(f(n))的概念，並利用對角線法證明了時間層級定理（Time Hierarchy Theorem）。

此後，許多研究者對複雜性理論作出了貢獻。期間重要的發現包括：對隨機演算法的去隨機化（derandomization）的研究，對近似演算法的不可近似性（hardness of approximation）的研究，以及互動式證明系統（Interactive proof system）理論和零知識證明（Zero-knowledge proof）等。特別的複雜性理論對近代密碼學的影響非常顯著，近期，複雜性理論的研究者又進入了博弈論領域，並創立了【演算法博弈論】（algorithmic game theory）這一分支。

再次驗證正反前輩所說的【數學】不是簡單，而是超級【複雜】！^__^

（Multi-choice＋algorithm＋cloud，應該可以讓正反前輩【受迫性三太子附身】，比較沒空要偶們【喀擦】……^+++++++++^）

綜覽全部討論

總　覽版　務政　經健康醫療軍　武理　財文　化藝　文科　技台灣的美旅　遊 PISA 娛　樂鄉　土公　民認　同副　刊哈　啦范氏網

竹縫
視界耳聾
世界泰伯
觀點 Joy
隨筆哈利
天地 Jerry C
鳥世界射水魚
天　空討海人
鏡　頭嘻笑
人間詩情
畫藝老工仔
思　維網網
相連歷史
庫存

* 討論區內之言論，不代表本園之立場，一切法律責任仍由發言者本人負責
* 如果您有任何不當言論，本園有權決定是否保留您所送貼的意見。