什么是算法復雜性(Algorithmic Complexity)？

算法復雜性是計算復雜性理論和算法信息理論的基本思想，在形式歸納中起著重要作用能產生字符串的最短和最有效的程序。雖然有無限多的程序可以產生任何給定的字符串，但一個程序或一組程序總是最短的。沒有算法可以找到輸...

算法復雜性是計算復雜性理論和算法信息理論的基本思想，在形式歸納中起著重要作用能產生字符串的最短和最有效的程序。雖然有無限多的程序可以產生任何給定的字符串，但一個程序或一組程序總是最短的。沒有算法可以找到輸出給定字符串的最短算法；這是計算復雜性理論的第一個結果之一。即使如此，我們也可以做出一個有根據的猜測。這個結果（字符串的計算復雜性）對于證明可計算性非常重要。因為任何物理對象或屬性在原則上都可以用一串比特描述為接近耗盡，對象和屬性可以說也有算法的復雜性。事實上，將現實世界中的對象的復雜性降低到生成對象作為輸出的程序，是看待科學事業的一種方式。我們周圍的復雜對象往往來自三個主要的生成過程：涌現，進化論和智能論，每一種方法產生的對象趨向于更高的算法復雜度。計算復雜性是理論計算機科學中常用的一個概念，用于確定計算各種數學和邏輯問題的解決方案的相對難度。超過400個復雜性類存在，并且不斷地發現額外的類。著名的P=NP問題涉及到其中兩個復雜類的性質復雜度課程包括的問題遠比任何一個人在數學到微積分中可能遇到的問題都要困難得多。在計算復雜性理論中，有許多可以想象到的問題需要幾乎無限的時間來解決。算法復雜性和相關概念在20世紀60年代由幾十個研究者Andrey Kolmogorov、Ray Solomonoff和Gregory Chaitin在60年代后期利用算法信息理論做出了重要貢獻，最小消息長度原則與算法復雜性密切相關，為統計歸納推理和機器學習提供了大量的基礎。

發表于 2020-09-18 03:20

閱讀 ( 781 )

分類：科學教育

你可能感興趣的文章

什么是吊橋(Hanging Bridge)？ 764 瀏覽

有哪些不同的環境管理資源(Different Environmental Management Resources)？ 556 瀏覽

澳門網址 1335 瀏覽

什么是Q開關(Q-Switching)？ 1618 瀏覽

肽公司有哪些不同類型(Different Types of Peptide Company)？ 607 瀏覽

什么是地震解釋(Seismic Interpretation)？ 839 瀏覽

亞太娛樂 698 瀏覽

優游平臺 763 瀏覽

拉烏爾定律是什么(Raoult's Law)？ 3215 瀏覽

四季娛樂 636 瀏覽

現金流游戲 1156 瀏覽

迪斯尼娛樂 573 瀏覽

什么是寒武紀(Cambrian Period)？ 760 瀏覽

什么是機械合成(Mechanosynthesis)？ 800 瀏覽

碳納米管有什么用途(Some Uses for Carbon Nanotubes)？ 626 瀏覽

什么是鸚鵡螺(Nautiloids)？ 889 瀏覽

什么是密封劑(Encapsulant)？ 751 瀏覽

什么是光學長凳(Optical Bench)？ 857 瀏覽

什么是天龍號太空飛機(the Skylon Spaceplane)？ 846 瀏覽

什么是超材料(Metamaterial)？ 1311 瀏覽

什么是造山運動(Orogeny)？ 1116 瀏覽

什么是仿生機器人(Biomimetic Robots)？ 711 瀏覽

什么是差示掃描量熱法(Differential Scanning Calorimetry)？ 1246 瀏覽

澳洲國際娛樂 759 瀏覽

什么是二乙烯三胺(Diethylenetriamine)？ 1148 瀏覽

什么是差示掃描量熱儀(Differential Scanning Calorimeter)？ 639 瀏覽

什么是Fusee(Fusee)？ 651 瀏覽

牌九規矩 982 瀏覽

什么是水楊醛(Salicylaldehyde)？ 1225 瀏覽

阿伏加德羅定律是什么(Avogadro's Law)？ 875 瀏覽

相關問題

0 條評論

請先登錄后評論

什么是算法復雜性(Algorithmic Complexity)？

你可能感興趣的文章

相關問題

0 條評論

作家榜 ?

推薦文章