计算理论计算理论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，

nn0，f(n)cg(n), 则称f(n)=O(g(n))，或g是f

的(渐进)上界。若f(n)<cg(n), 则称f(n)=o(g(n))

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

计算理论第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。◼平...

展开>> 收起<<

计算理论计算理论6章复杂性1.pdf

共21页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

计算理论计算理论6章复杂性1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

计算理论计算理论6章 复杂性1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

计算理论计算理论6章复杂性1