计算理论计算理论6章 复杂性1
VIP免费
2025-01-13
0
0
408.49KB
21 页
5.9玖币
侵权投诉
计算理论
第6章 计算复杂性
算法（Algrithm）
◼算法 处处停机图灵机
◼算法是直觉概念
◼图灵机是数学概念
◼= 是可以严格证明的定理
◼ 可以作为定义, 不能证明
◼丘奇-图灵论题 (Church-Turing Thesis)
◼算法的直觉概念 = 图灵机算法
复杂性理论(Complexity)
◼时间复杂性（Time Complexity）
◼空间复杂性（Space Complexity）
时间复杂性
◼复杂性度量
◼定义：M是一个在所有输入上停机的DTM，M
的时间复杂度是一个函数f:N→N，f(n)是M在
所有输入长度为n的输入上运行的最大步数。
◼若M的时间复杂度是f(n)，则称M运行时间为
f(n)，M是f(n)时间TM。
◼平均情况复杂度、最坏情况复杂度
记法
◼渐近法
◼定义：设f和g是函数, f,g:N→R+.若c,n0，
nn0，f(n)cg(n), 则称f(n)=O(g(n))，或g是f
的(渐进)上界。若f(n)<cg(n), 则称f(n)=o(g(n))
g
f
cg
摘要：
展开>>
收起<<
计算理论第6章计算复杂性算法（Algrithm）◼算法处处停机图灵机◼算法是直觉概念◼图灵机是数学概念◼=是可以严格证明的定理◼可以作为定义,不能证明◼丘奇-图灵论题(Church-TuringThesis)◼算法的直觉概念=图灵机算法复杂性理论(Complexity)◼时间复杂性（TimeComplexity）◼空间复杂性（SpaceComplexity）时间复杂性◼复杂性度量◼定义：M是一个在所有输入上停机的DTM，M的时间复杂度是一个函数f:N→N，f(n)是M在所有输入长度为n的输入上运行的最大步数。◼若M的时间复杂度是f(n)，则称M运行时间为f(n)，M是f(n)时间TM。◼平...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
分类：计算机
价格：5.9玖币
属性：21 页
大小：408.49KB
格式：PDF
时间：2025-01-13
作者详情
-
Optimal Persistent Monitoring of Mobile Targets in One Dimension Jonas Hall1 Sean Andersson12 Christos G. Cassandras13 Abstract This work shows the existence of opti-5.9 玖币0人下载
-
Optimal metabolic strategies for microbial growth in stationary random environments Anna Paola Muntoni and Andrea De Martino5.9 玖币0人下载
相关内容
-
行政事业单位内部控制报告-关于印发编外聘用人员管理制度和编外聘用人员年度考核制度
分类：办公文档
时间：2025-03-03
标签：无
格式：DOC
价格：5.9 玖币
-
行政事业单位内部控制报告-风险评估管理制度
分类：办公文档
时间：2025-03-03
标签：无
格式：DOCX
价格：5.9 玖币
-
行政事业单位内部控制报告-采购管理内部控制制度
分类：办公文档
时间：2025-03-03
标签：无
格式：DOCX
价格：5.9 玖币
-
行政事业单位内部控制报告-部署单位内部控制专题培训和风险评估工作会议纪要
分类：办公文档
时间：2025-03-03
标签：无
格式：DOC
价格：5.9 玖币
-
行政事业单位内部控制报告-关键岗位轮岗及专项审计制度
分类：办公文档
时间：2025-03-03
标签：关键
格式：DOCX
价格：5.9 玖币
渝公网安备50010702506394
