第10章NP完全问题课件.ppt

上传人:晟*** 文档编号:14565706 上传时间:2022-11-01 格式:PPT 页数:21 大小:261KB
下载 相关 举报
第10章NP完全问题课件.ppt_第1页
第1页 / 共21页
第10章NP完全问题课件.ppt_第2页
第2页 / 共21页
第10章NP完全问题课件.ppt_第3页
第3页 / 共21页
第10章NP完全问题课件.ppt_第4页
第4页 / 共21页
第10章NP完全问题课件.ppt_第5页
第5页 / 共21页
点击查看更多>>
资源描述

110.1 引言10.2 P 类10.3 NP 类10.4 NP 完全问题10.5 co-NP 类( 略)10.6 NPI 类( 略)10.7 四种类之间的关系( 略)10.x 近似算法初步210.1 引言 在前面的各章中,我们对一些算法的设计和分析进行在前面的各章中,我们对一些算法的设计和分析进行了讨论,这些算法的运行时间可用低次多项式来表示。了讨论,这些算法的运行时间可用低次多项式来表示。在这一章,我们将注意力集中在这样一类问题,这些问在这一章,我们将注意力集中在这样一类问题,这些问题至今没有找到有效算法,而且今后也有可能证明它们题至今没有找到有效算法,而且今后也有可能证明它们不存在有效算法。不存在有效算法。 设设是任意问题,如果对该问题存在一个算法,它的是任意问题,如果对该问题存在一个算法,它的时间复杂性是时间复杂性是O(nO(nkk),其中,其中nn是输入大小、是输入大小、kk是非负整数,是非负整数,我们说问题我们说问题存在多项式时间算法。现实世界的许多问存在多项式时间算法。现实世界的许多问题并不属于这个范畴,因为求解这些问题耗费的时间需题并不属于这个范畴,因为求解这些问题耗费

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育教学资料库 > 课件讲义

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。