什么是算法复杂性(Algorithmic Complexity)？

算法复杂性是计算复杂性理论和算法信息理论的基本思想，在形式归纳中起着重要作用能产生字符串的最短和最有效的程序。虽然有无限多的程序可以产生任何给定的字符串，但一个程序或一组程序总是最短的。没有算法可以找到输...

算法复杂性是计算复杂性理论和算法信息理论的基本思想，在形式归纳中起着重要作用能产生字符串的最短和最有效的程序。虽然有无限多的程序可以产生任何给定的字符串，但一个程序或一组程序总是最短的。没有算法可以找到输出给定字符串的最短算法；这是计算复杂性理论的第一个结果之一。即使如此，我们也可以做出一个有根据的猜测。这个结果（字符串的计算复杂性）对于证明可计算性非常重要。因为任何物理对象或属性在原则上都可以用一串比特描述为接近耗尽，对象和属性可以说也有算法的复杂性。事实上，将现实世界中的对象的复杂性降低到生成对象作为输出的程序，是看待科学事业的一种方式。我们周围的复杂对象往往来自三个主要的生成过程：涌现，进化论和智能论，每一种方法产生的对象趋向于更高的算法复杂度。计算复杂性是理论计算机科学中常用的一个概念，用于确定计算各种数学和逻辑问题的解决方案的相对难度。超过400个复杂性类存在，并且不断地发现额外的类。著名的P=NP问题涉及到其中两个复杂类的性质复杂度课程包括的问题远比任何一个人在数学到微积分中可能遇到的问题都要困难得多。在计算复杂性理论中，有许多可以想象到的问题需要几乎无限的时间来解决。算法复杂性和相关概念在20世纪60年代由几十个研究者Andrey Kolmogorov、Ray Solomonoff和Gregory Chaitin在60年代后期利用算法信息理论做出了重要贡献，最小消息长度原则与算法复杂性密切相关，为统计归纳推理和机器学习提供了大量的基础。

发表于 2020-09-18 03:20

阅读 ( 931 )

分类：科学教育

你可能感兴趣的文章

什么是吊桥(Hanging Bridge)？ 893 浏览

有哪些不同的环境管理资源(Different Environmental Management Resources)？ 663 浏览

澳门网址 1456 浏览

什么是Q开关(Q-Switching)？ 1764 浏览

肽公司有哪些不同类型(Different Types of Peptide Company)？ 706 浏览

什么是地震解释(Seismic Interpretation)？ 1414 浏览

亚太娱乐 818 浏览

优游平台 1372 浏览

拉乌尔定律是什么(Raoult's Law)？ 3398 浏览

四季娱乐 753 浏览

现金流游戏 1714 浏览

迪斯尼娱乐 828 浏览

什么是寒武纪(Cambrian Period)？ 1010 浏览

什么是机械合成(Mechanosynthesis)？ 999 浏览

碳纳米管有什么用途(Some Uses for Carbon Nanotubes)？ 987 浏览

什么是鹦鹉螺(Nautiloids)？ 1087 浏览

什么是密封剂(Encapsulant)？ 854 浏览

什么是光学长凳(Optical Bench)？ 1043 浏览

什么是天龙号太空飞机(the Skylon Spaceplane)？ 977 浏览

什么是超材料(Metamaterial)？ 1503 浏览

什么是造山运动(Orogeny)？ 1251 浏览

什么是仿生机器人(Biomimetic Robots)？ 820 浏览

什么是差示扫描量热法(Differential Scanning Calorimetry)？ 1388 浏览

澳洲国际娱乐 850 浏览

什么是二乙烯三胺(Diethylenetriamine)？ 1285 浏览

什么是差示扫描量热仪(Differential Scanning Calorimeter)？ 895 浏览

什么是Fusee(Fusee)？ 787 浏览

牌九规矩 1089 浏览

什么是水杨醛(Salicylaldehyde)？ 1404 浏览

阿伏加德罗定律是什么(Avogadro's Law)？ 1014 浏览

相关问题

0 条评论

请先登录后评论

什么是算法复杂性(Algorithmic Complexity)？

你可能感兴趣的文章

相关问题

0 条评论

作家榜 »

推荐文章