算法时间复杂度和NP问题简介
2024-10-19 03:34:36
这里主要简单说一下算法的时间复杂度和NP问题简介,毕竟分析算法的时间复杂度上界有助于分析算法的好坏,分析算法好坏也有助于分析是否还有更好的算法;
一、时间复杂度:
一般关心的还有递归问题中的时间复杂度:(参考:http://blog.csdn.net/so_geili/article/details/53444816)
例:
二、NP(Non-determinstic polynnomial)问题:
P类问题:可以在多项式时间内使用确定性算法求解的判定问题;
NP类问题:可以在多项式时间内使用非确定性算法求解的判定问题;
NPC问题(NP完全问题):NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的;
注意:(1)这里的多项式时间的时间针对的是问题的规模;
(2)我们将可以在多项式时间内求解的问题称为“易”问题,将需要在指数时间内求解的问题称为“难”问题;
(3)从定义很容易发现P属于NP,但P是不是NP的真子集,这个问题目前是世界七大难题之一;
(4)判定问题的定义可以参见下面这个例子:
最新文章
- HTML中为何p标签内不可包含div标签?那哪些块元素里面不能放哪些块元素呢?
- Nginx配置加入css缓存配置后,css等文件not found
- Obiee11g变量
- linux 下进程通讯详解
- Centos5.8 安装SVN并配置HTTP访问
- 查看/修改 Linux 时间和时区
- java 导入自定义类
- byte[] 与字符串转换
- (剑指Offer)面试题15:链表中倒数第k个结点
- win7无法识别U盘,驱动信息:该设备的驱动程序未被安装。 (代码 28)
- struts2配置文件struts.xml的简介
- Spring mvc 简单异常配置jsp页面
- Mongodb安装和基本命令
- PL/SQL Developer下设置“长SQL自己主动换行”
- java跳过构造方法新建对象
- [图形学] 习题8.6 线段旋转后使用Cohen-Sutherland算法裁剪
- 制作 alipay-sdk-java包到本地仓库
- 折腾Java设计模式之状态模式
- [Swift]LeetCode1027. 最长等差数列 | Longest Arithmetic Sequence
- jquery中prop()和attr()用法
热门文章
- 洛谷 P3297 [SDOI2013]逃考 解题报告
- suoi37 清点更多船只 (卡空间线段树)
- bzoj3277 串 (后缀数组+二分答案+ST表)
- [NOI2015]寿司晚宴——状压dp
- 斯坦福大学公开课机器学习:梯度下降运算的学习率a(gradient descent in practice 2:learning rate alpha)
- GBDT原理详解
- 到浏览器顶部的获取js和jquery
- 修改placeholder样式
- JAVA记录-POST与GET方式区别
- .NET MVC中的ActionResult