P问题,NP问题,NPC问题,NP-hard问题
2024-08-27 15:50:20
1.P问题:一个问题能找到一个在多项式时间里解决他的算法
- 多项式时间(o(1),o(lgn),o(n的a次方))
- 非多项式时间 o(a的n次方) o(n!)
2.NP问题:在多项式时间找不到问题的解,但可在多项式时间验证问题的解(所有P问题都是NP问题)
3.NPC问题:存在一个NP问题,所有其他NP问题都可以约化为它
①是一个NP问题
②所有NP问题都可约化为它
一元二次方程可以约化一元一次方程(一元一次方程(简单问题)可以约化为一元二次方程(难问题))
问题A可以约化为问题B
B的复杂度>A的复杂度,问题B解决了,问题A也就解决了
4.NP-hard问题:不一定是NP问题,但所有NP问题可以约化成他
- 这类问题不能用精确算法求解,需要寻找一个有效的近似算法(售货员旅行问题)
最新文章
- Oracle中已有数据的字段类型修改
- 主成分分析(PCA)特征选择算法详解
- javascript中使用循环链表实现约瑟夫环问题
- 基本概率分布Basic Concept of Probability Distributions 8: Normal Distribution
- HDU 4006 优先队列
- 时隔两年最近再次折腾opensuse 的一些笔记 - opensuse linux java service shell
- iOS 7.0获取iphone UDID 【转】
- hadoop2 作业执行过程之map过程
- OpenJudge 2680 化验诊断 C++
- 判断URL是否存在
- java学习阶段三:运算符和结构学习
- linux18.04+jdk11.0.2+hadoop3.1.2部署伪分布式
- Mysql在sql中截取时间类型字段的年月日
- $Django 发送邮件--django封装模块和python内置SMTP模块
- 快速准备(复制替换)一套新测试环境,CentOS7 MySQL相关配置
- 怎么理解Python画图中的X,y
- 运行fdisk命令时,弹出 bash:fdisk:command not found
- 危机边缘第一季/全集Fringe迅雷下载
- SPARK数据类型
- 腾讯 OCR 情况
热门文章
- vs2017安装cuda9.0编译默认示例失败解决方法
- Azure 中 Windows 虚拟机的大小
- ajax status 错误
- Jmeter用于接口测试中【接口耦合关联的实现】
- NIO 学习笔记
- 根据字体多少使UILabel自动调节尺寸
- 【Python】os.path.isfile()的使用方法汇总
- CentOS7安装Java
- js实现千位分隔符——str.replace()用法
- BZOJ2744:[HEOI2012]朋友圈(最大团,乱搞)