多项式时间

✍ dations ◷ 2025-11-26 08:04:27 #计算复杂性理论,计算资源

多项式时间（英语：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的缩写）。

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

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

相关

面糊面糊（英语：Batter），一种烹调常用的半固混合物，通常用面粉与水，或者是鸡蛋、牛奶等液体混合而成。也可以加入诸如泡打粉之类的膨松剂，或者是用碳酸水混合面粉，以在烹调后产生更为蓬松
天文台环路一号天文台环路一号（英语：Number One Observatory Circle）是美国副总统的官邸。它位于美国华盛顿特区美国海军天文台的东北开阔地，始建于1893年。美国海军作战部长非常喜欢这套房子，
锢囚锋囚锢锋是锋的一种，是由于冷锋追上暖锋，或者两条冷锋迎面相遇而成（也有同一条冷锋的两段迎面相遇而形成的）。锢囚锋的形成经常发生在温带气旋的成熟阶段，通常出现在中高纬度地区。
休金诺区休金诺区（俄语：Щу́кино；拉丁字母转写：Shchukino）是位于莫斯科中央直辖市西北行政区的一个辖区，北部和波克罗夫-斯特列什捏沃区（俄语：Покровское-Стрешнев
戴进贤戴进贤（1680年－1746年），字嘉宾，德国天文学家、数学家、耶稣会在华传教士，原名伊格纳茨·柯格勒（Ignaz Kögler）。他曾在清廷供职29年之久。戴进贤出生于德国巴伐利亚莱希河畔兰茨贝
巴塞尔造纸印刷博物馆巴塞尔造纸印刷博物馆（Basler Papiermühle）是位于瑞士巴塞尔的一座博物馆，以造纸和印刷为展示主题。巴塞尔造纸印刷博物馆的建筑有500年的历史，曾是一座造纸厂，也是瑞士的文化遗
马克·温伯格马克·温伯格(英语：Mark A. Weinberger)是一位美国企业家。出生于美国斯克兰顿 (宾夕法尼亚州)，1983年毕业于埃默里大学，1987年毕业于凯斯西储大学，1991年毕业于乔治城大学法律
名字古怪的小矮人儿《名字古怪的小矮人儿》（德语：，音译：龙佩尔施迪尔钦），又译《侏儒妖》，是格林兄弟收集的一则童话，由格林兄弟最先收录于1812年的首版《儿童与家庭故事集》之中，其后又历经数次修订，于18
曹璜 (万历进士)《大云集》曹璜（？－？），字维章，又字于渭，号础石，山东青州府益都县人，民籍，明朝政治人物。著有《大云集》。万历十年（1582年）壬午科乡试五十五名举人。万历十四年（1586年）丙戌科进士。授户部主
三秋里步三秋里步（1994年8月24日－）是日本艺人，为大型偶像团体吉本坂46成员，曾为女子偶像团体NMB48 Team N前成员、并曾兼任AKB48 Team 4成员，京都府出身。本名小谷里步（小谷里歩／こたにり