如何度量复杂度
如何 复杂度 度量
2023-09-11 14:18:43 时间
我们以度量复杂度的3种方法作为本文的结束:
- / 用逻辑深度度量复杂性
- 为了更加接近我们对复杂性的直觉,数学家班尼特在20世纪80年代初提出了逻辑深度(logical depth)的概念。
- 一个事物的逻辑深度是对构造这个事物的困难程度的度量。
- 高度有序的A、C、G、T序列显然很容易构造。
- 同样,如果我要你给我一个A、C、G、T的随机序列,你也很容易就可以做出来,用个硬币或骰子就可以了。
- 但如果我要你给我一个能够生成可发育的生物的DNA序列,如果不偷看真正的基因组序列,别说你,任何一个生物学家都会觉得很难办到。
- 用班尼特的话说,“有逻辑深度的事物……从根本上必须是长时间计算或漫长动力过程的产物,否则就不可能产生。”
- / 用算法信息量度量复杂性
- 物理学家盖尔曼(Murray Gell-Mann)提出了一种称为“有效复杂性(effective complexity)”的相关度量,更符合我们对复杂性的直观认识。
- 盖尔曼认为任何事物都是规则性和随机性的组合。
- 例如,序列1就有非常简单的规则性:重复的AC模式。序列2则没有规则性,因为它是随机产生的。与之相比,生物的DNA则有一些规则性(例如,基因组不同部分之间存在重要关联),也有一些随机性(例如DNA中的垃圾)。
- 序列2处于另一个极端,因为是随机的,所以没有规则性。因而也不需要信息来描述,虽然序列本身的算法信息量是最大的,序列规则性的算法信息量——其有效复杂性——却为零。
- 简而言之,就如我们希望的,最有序和最随机的事物有效复杂性很低。
- / 用统计复杂性度量复杂性
- 我们也可以用统计复杂性(statistical complexity)的量,度量用来预测系统将来的统计行为所需的系统过去行为的最小信息量。
- 例如,序列1的信息源模型可以很简单:“重复AC”;因此其统计复杂性很低。
- 然而,与熵或算法信息量不同,对于产生序列2的信息源也可以有很简单的模型:“随机选择A、C、G或T。”这是因为统计复杂性模型允许包含随机选择。
- 统计复杂性的度量值是预测系统行为的最简单模型的信息量。
- 与有效复杂性一样,对于高度有序和随机的系统,统计复杂性的值都很低,介于两者之间的系统则具有高复杂性,与我们的直觉相符。
作者:读饭
链接:https://www.jianshu.com/p/3c0be8dddf37
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- 如何可视化编写和编排你的 K8s 任务
- [转载]我们是如何做好前端工程化和静态资源管理
- 如何从建表方面展示自己能力--转
- Python中,如何初始化不同的变量类型为空值
- 78. 如何通过 url 保持 SAP UI5 搜索的状态,让其支持书签功能
- 如何开发一个 SAP UI5 Tools 的自定义中间件扩展 - Custom Middleware Extension
- 如何计算并测量ABAP及Java代码的环复杂度Cyclomatic complexity
- SAP S/4HANA是如何通过SADL框架加CDS view读取销售订单数据的
- SAP UI5 应用开发教程之八十七 - 如何让 SAP UI5 Mock 服务器支持自定义 url 参数试读版
- 二进制如何转十进制,十进制如何转二进制
- 【FastDFS】如何打造一款高可用的分布式文件系统?这次我明白了!!
- 谈谈如何学习自动化测试
- 数据结构与算法_27 _ 递归树:如何借助树来求解递归算法的时间复杂度?
- 数据结构与算法_03 _ 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗
- 33. 如何找出 SAP Fiori Launchpad 里点击 tile 之后,读取业务数据调用的是哪个 SAP 后台系统的 OData 服务
- Linux当中如何隐藏和查看进程
- 【计算机架构】如何计算 CPU 动态功耗
- 2020款Macbook Pro忘了激活锁账户密码如何向苹果申请解锁