多项式时间

✍ dations ◷ 2025-12-01 08:57:04 #计算复杂性理论,计算资源

多项式时间（英语：Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间 $m(n)$ $m(n)$ 不大于问题大小 $n {\displaystyle n}$ $n$ 的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。

以数学描述的话，则可说 $m(n)=$ $m(n)=$ O $(n^{k})$ $(n^{k})$ ，此 $k {\displaystyle k}$ $k$ 为一常量值（依问题而定）。

数学家有时把“如多项式时间长的算法”视为快速计算，相对应的是超多项式时间，表示任何多项式时间的输入数目只要够大，超多项式时间所需的解题时间终究会大大超过任何多项式时间的问题。指数时间就是一例。

可以在决定型依序机器上（例如图灵机）以多项式时间解决的决定性问题，其属于的复杂度类被称为P。可以在多项式时间验证答案的决定性问题称为NP。而NP也是可以在非确定型图灵机以多项式时间解决的问题（NP两字为Non-deterministic Polynomial的缩写）。

多项式时间在决定型机器上是最小的复杂度类，且在机器模型改变时依旧强韧，且也是可在副程序组合过程中保持封闭的类别。

强多项式时间指的是此问题的运算时间不因输入资料的数字大小而变动，而是依照输入资料的结构复杂度（例如图论中的顶点数量）。

相关

纳博特囊肿纳博特囊肿（nabothian cyst, nabothian follicle），也称纳囊、宫颈腺囊肿、宫颈腺体囊肿、子宫颈囊肿，是一类位于宫颈表面的囊肿。当外宫颈复层鳞状上皮生长覆盖过单层柱状上皮上
加拿大盖尔德纳国际奖加拿大盖尔德纳国际奖（Canada Gairdner International Award），原名盖尔德纳基金会国际奖（Gairdner Foundation International Award），是一个始于1959年的学术奖，每年授予在3到6位在
Newcastle upon Tyne坐标：54°58′26″N 1°36′48″W / 54.9740°N 1.6132°W / 54.9740; -1.6132泰恩河畔纽卡斯尔（英语：Newcastle upon Tyne 英式发音： i/njuːˈkɑːsələpɒnˌtaɪn/；本地发
幼儿幼儿也称为幼童，是人类发展的阶段之一。可能包括学步期（英语：toddlerhood）及之后，一直到学龄前的一段时间，此一阶段也常称为是玩耍期（Play age）；是儿童阶段中较前期的部分。在心理学
沃尔德马尔·巴吉尔沃尔德马尔·巴吉尔（德语：Woldemar Bargiel，1828年10月3日－1897年2月23日），德国作曲家，音乐学家。他是克拉拉·舒曼的异父弟，自幼受到舒曼和门德尔松的培养，后到莱比锡音乐学院学习，毕
艾哈迈德沙·卡扎尔艾哈迈德沙·卡扎尔（波斯语：احمد شاه قاجار；英语：Ahmad Shah Qajar，1898年1月21日－1930年2月21日）是1909年7月16日至1925年10月31日在位的伊朗卡扎尔王朝沙阿，也是王朝
霍舍姆坐标：51°03′43″N 0°19′30″W / 51.062°N 0.325°W / 51.062; -0.325霍舍姆（Horsham）是英格兰萨塞克斯郡的一个城市，位于伦敦南南西31英里（50千米），布莱顿西北18.5英里（30千米），
千禧曼波《千禧曼波》（英语：）是台湾导演侯孝贤于2001年发行的电影作品，并获得该年戛纳影展技术大奖。Vicky在2011年的时候描述她10年前的故事，她当时与男友小豪同居，小豪不工作只靠Vicky在
安格尔函数安格尔函数是英国数学家安格尔在1855年首先研究的积分函数 J ν (
英国的海岸线有多长？统计自相似和分数维度《英国的海岸线有多长？统计自相似和分数维度》（英语：），是由法国、美国数学家本华·曼德博（Benoît B. Mandelbrot）撰写的论文，最初在1967年于《科学》发表。在这篇论文内曼德博讨论