计算理论计算理论6章 复杂性1
VIP免费
2025-01-13
2
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交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
工程建设招标投标合同（附件）VIP免费
2024-11-15 16 -
工程建设招标投标合同（动员预付款银行保证书）VIP免费
2024-11-15 11 -
工程建设招标设标合同条件（第1部分）VIP免费
2024-11-15 11 -
工程建设招标设标合同合同条件（第3部分）VIP免费
2024-11-15 10 -
工程建设招标设标合同合同条件（第2部分）VIP免费
2024-11-15 13 -
工程建设监理委托合同VIP免费
2024-11-15 14 -
工程建设监理合同标准条件VIP免费
2024-11-15 11 -
工程技术资料目录VIP免费
2024-11-15 13 -
工程技术咨询服务合同VIP免费
2024-11-15 13 -
工程建设招标投标合同（投标邀请书）VIP免费
2024-11-15 35
分类：计算机
价格：5.9玖币
属性：21 页
大小：408.49KB
格式：PDF
时间：2025-01-13
渝公网安备50010702506394
