伪多项式时间算法Pseudo-polynomial Algorithms-----geeksforGeek 翻译
2024-10-20 11:46:42
原创翻译加学习笔记，方便国人学习算法知识！
原文链接http://www.geeksforgeeks.org/pseudo-polynomial-in-algorithms/
什么是伪多项式？
当一个算法的最坏时间复杂度是依据输入的数量级的时候，我们就称算法的时间复杂偶是伪多项式时间（给一个wiki上的解释可能更好理解 若一个数值算法的时间复杂度可以表示为输入数值规模N的多项式，但其运行时间与输入数值规模N的二进制位数呈指数增长关系，则称其时间复杂度为伪多项式时间。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的幂from wiki )
例如：统计一个数组中所有正数的出现频率。算法是先找到最大的数max，然后从1到max遍历没一个数，找到这个数在数组中的出现频率。这个算法需要的时间是取决于这个数组中最大的数的大小，所以说这个算法是伪多项式时间。换句话说，一个算法的时间复杂度只是根据输入元素的多少的话，我们认为这个算法是多项式时间算法。
伪多项式和NP完全问题
有一些NP问题是有伪多项式时间的解法的，例如：0-1背包问题的动态规划解法，子集和的问题（找出数组里子集的和等于某个值的问题）， 切分问题。这都是伪多项式时间。如果一个NP完全问题有伪多项式时间的解法，那么我们称这种问题叫弱NP完全问题。
最新文章
- yield生成器及字符串的格式化
- ThreadLocal的理解
- Tyvj P1175 机器人
- Google地图实现
- Linux学习笔记(20) Linux系统管理
- ch2 创建和销毁对象
- 进入IT企业必读的200个.NET面试题
- 基础学习day07---面向对象三---继承，接口与 抽象类
- ARC指南1 - strong和weak指针
- 【CF】223 Div.1 C Sereja and Brackets
- Eclipse运行Tomcat7源码
- 弗洛伊德(Floyd)算法
- inline函数和一般的函数有什么不同
- C编译: makefile基础
- OpenGL中glUniform1i使用
- Power BI行级别安全性(数据权限管理)
- PL/SQL简单使用——导入、导出数据表
- Spring 源码分析 spring-core 篇
- Python_xml
- [Java web]Spring+Struts2+Hibernate整合过程（2）