伪多项式时间 Pseudo-polynomial time
2024-08-24 05:44:13
2018-03-15 14:20:08
伪多项式时间:如果一个算法的传统时间复杂度是多项式时间的,而标准时间复杂度不是多项式时间的,则我们称这个算法是伪多项式时间的。
想要理解“伪多项式时间”,我们需要先给出“多项式时间”的一个清楚的定义。
对于“多项式时间”,我们的直观概念是时间复杂度,其中是一常数。比如,选择排序的时间复杂度是,是多项式时间;暴力解决TSP问题的时间复杂度是,不是多项式时间。我们称这种时间复杂度为“传统时间复杂度”。
我们通常认为传统时间复杂度中的变量表示数据的输入规模。比如,选择排序中,指待排序数组中元素的个数;TSP问题中表示图中节点的数量。但是,这些所谓的输入规模,仅仅是直观的定义,并不足够严谨。为了标准化这些,在计算标准时间复杂度时,我们给出了输入规模的标准定义:
一个问题的输入规模是保存输入数据所需要的bit位数。
了解了输入规模的定义,我们来看“多项式时间”的标准定义:
对于一个问题,在输入规模为x的情况下,如果一个算法能够在O()时间内解决此问题,则我们称此算法是多项式时间的,其中为一常数。
排序问题:用选择排序对元素个数为的数组进行排序时,传统时间复杂度为。输入规模,因此,得到的标准时间复杂度是,仍然是多项式时间。因为这的n是只输入数据的数目。
素数测试:给定数字 n,通过从 2 到根号 n 的整数遍历,判断 n 是否为素数。看似时间复杂度是O(n),但是这里的n是输入数字的大小,真实的输入规模为 x = logn,因此实际的时间复杂度是O(x ^ 2),是指数级的时间复杂度。这就是个伪多项式时间复杂度。
最新文章
- 求数组的长度 C
- hdu Super Jumping
- 基于jQuery带备忘录功能的日期选择器
- sublime3 ctl+b无效
- 北风风hadoop课程体系
- centos7用户,组及文件权限管理
- 获取 wx.getUserInfo 接口后续将不再出现授权弹窗,请注意升级(微信小程序开发)
- 使用CompletionService结合ExecutorService批处理调用存储过程任务实例
- 怎么安装Scrapy框架以及安装时出现的一系列错误(win7 64位 python3 pycharm)
- Python 中的object takes no parameters错误
- CF280C Game on Tree
- SQL手工注入入门级笔记(更新中)
- [转] 隐马尔可夫(HMM)、前/后向算法、Viterbi算法 再次总结
- Linux 默认目录
- Beautiful Soup 学习手册
- 3. tomcat 内存设置
- java项目发布
- sql练习(针对Mysql)
- 【RL系列】马尔可夫决策过程中状态价值函数的一般形式
- 3D游戏与计算机图形学中的数学方法-四元数
热门文章
- 问答项目---用户注册的那些事儿(PHP验证)
- java之面向对象三大特征(封装,继承,多态)
- 170613、Spring整合RabbitMQ实例
- 沈阳网络赛F-Fantastic Graph【贪心】or【网络流】
- spring自定义事务同步器(二):借助redisson实现自己的同步器
- (1.4)DML增强功能-Output
- MFC截图和界面刷新相关问题
- 204-React DOM 元素
- android ReactNative之Cannot find entry file index.android.js in any of the roots
- js文件被浏览器缓存