多项式时间

✍ dations ◷ 2025-09-11 08:13:20 #计算复杂性理论,计算资源

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

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

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

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

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

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

相关

  • 风湿病学人体解剖学 - 人体生理学 组织学 - 胚胎学 人体寄生虫学 - 免疫学 病理学 - 病理生理学 细胞学 - 营养学 流行病学 - 药理学 - 毒理学风湿病学或称风湿病专科(英语:Rheumatol
  • 大写高度在西文字体排印学中,大写字高(英语:Cap height)是指某种字体中,位于基线(baseline)以上的大写字母的高度。尤其指相对平顺的字母“H”和“I”的高度。因为圆型的字母“O”和尖形字
  • 薄伽梵歌《薄伽梵谭》(梵语:भगवद् गीता,转写:Bhagavad Gītā,字面意思是“至尊神的颂谭、颂赞、赞歌”),又称为薄伽梵颂、薄伽梵卡、薄伽梵歌、博伽梵歌,是印度教的重要经典,叙述了
  • 扶沟县扶沟县,是中华人民共和国河南省周口市下辖的一个县。面积1163平方公里,2002年人口71万人。县政府驻城关镇。扶沟县往西是许昌,往北有开封,地处豫东平原,黄泛区腹地。全县总人口70
  • 加罗语加罗语(Gallo)是法国的一种语言。加罗语属罗曼语族,是奥依语之一。主要在上布列塔尼地区使用。
  • 波萨利门波萨利门(Porta Borsari)是意大利北部城市维罗纳的一座古罗马城门。它建于公元1世纪,可能是建在公元前1世纪的旧城门之上。皇帝加里恩努斯在位时,该门在265年重建。Postumia古道
  • 圆灰蝶亚科圆灰蝶亚科(学名:)是蝴蝶凤蝶总科灰蝶科里的一个亚科。物种分布在亚洲和非洲。曾经分级为亚科的两个分布于非洲的灰蝶分类——琳灰蝶亚科和盆灰蝶亚科——如今归入圆灰蝶亚科,各
  • 亚历山大·谢苗诺维奇·卡普托亚历山大·谢苗诺维奇·卡普托(俄语:Александр Семёнович Капто,1933年4月14日-2020年4月19日),乌克兰出身的俄罗斯社会学家、政治学家、外交官,前苏联驻古
  • 武村正义武村正义(1934年8月26日-),日本的自治官僚、政治家。出身于滋贺县蒲生郡玉绪村(八日市市、现东近江市)的农民家庭。东京大学教育学部、经济学部毕业。先后担任八日市市市长、滋贺
  • 伊朗大学列表本列表旨在列出位于伊朗的大学: