多项式时间，多项式的时间和空间是什么

1，多项式的时间和空间是什么

时间和空间是有成比的！一个空间的存在和时间有密切关联！

多项式的时间和空间是什么

2，多项式时间的介绍

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

多项式时间的介绍

3，多项式时间的定义

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

多项式时间的定义

4，多项式时间的解释

数学家有时把“比多项式时间长的算法”视为快速计算，相对应的是超多项式时间，表示任何多项式时间的输入数目只要够大，超多项式时间所需的解题时间终究会大大超过任何多项式时间的问题。指数时间（Exponential time）就是一例。超多项式时间：O(c^f(n))，其中c为大于1的常数，f(n)大于常数，小于线性。可以在决定型依序机器上（例如图灵机）以多项式时间解决的决定性问题，其属于的复杂度类被称为P。可以在多项式时间验证答案的非决定性问题称为NP。而NP也是可以在非确定型图灵机以多项式时间解决的问题（NP两字为Non-deterministic Polynomial的缩写）。多项式时间在决定型机器上是最小的复杂度类别，且在机器模型改变时依旧强韧，且也是可在副程式组合过程中保持封闭的类别。强多项式时间指的是此问题的运算时间不因输入资料的数字大小而变动，而是依照输入资料的结构复杂度（例如图中的顶点数量）。

5，急多项式时间内算法

多项式时间就是指时间复杂度是个多项式或者说,就是这个程序运行的时间随着数据规模n变化的函数为f(n)那么,f(n)是个多项式函数,那么就可以说是控制在多项式之内.

定义：若存在一个常数c，使得对于所有n>=0，都有|f(n)| <= c*|g(n)|，则称函数f(n)是o(g(n))。时间复杂度是o(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。不能够这样限制时间复杂度的算法被称为指数时间算法。　　例如：时间复杂度为o(nlog(n))、o(n^3)的算法都是多项式时间算法，时间复杂度为o(n^log(n))、o(n!)、o(2^n)的算法是指时间算法。　　一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并将这类问题的集合记为p，因此多项式时间可解问题就称为p类问题。　　一个问题如果没有找到多项式时间算法，那么直觉上它是“难解”的，但又往往无法证明多项式时间算法的不存在性。由于在寻找有效算法上的失败未必一定意味着这样的算法不存在，这就给理论工作者带来了一个难题：一方面证明一个问题不存在多项式时间算法是困难的，至今尚未给出；另一方面有越来越多的问题无法给出多项式时间算法。同时，理论工作者又渴望解决此难题。为此，在20世纪70年代提供了一个漂亮的理论，它把这种失败归结为一个深刻的数据猜想，这个理论就是np-完全性理论。　　定义：给定一个判定问题，如果存在一个算法，对任何一个答案为“是”的实例i。该算法首先给出一个猜想，该猜想规模不超过i的输入长度的某个多项式函数，且验证猜想的正确性仅需多项式时间，则称该问题属于np类。　　定义：如果np类中所有问题都可以多项式时间归约到np类中某个问题x，则称x是np-完全问题。　　定义：如果某优化问题x的判定问题是np-完全的，则称问题x是np-难的；如果x的判定问题是强np-完全的，则称x是强np-难的。

6，什么是伪多项式时间算法

polynomial-timealgorithm多项式时间算法定义：若存在一个常数C，使得对于所有n>=0，都有|f(n)|<=C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。不能够这样限制时间复杂度的算法被称为指数时间算法。例如：时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指时间算法。一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。一个问题如果没有找到多项式时间算法，那么直觉上它是“难解”的，但又往往无法证明多项式时间算法的不存在性。由于在寻找有效算法上的失败未必一定意味着这样的算法不存在，这就给理论工作者带来了一个难题：一方面证明一个问题不存在多项式时间算法是困难的，至今尚未给出；另一方面有越来越多的问题无法给出多项式时间算法。同时，理论工作者又渴望解决此难题。为此，在20世纪70年代提供了一个漂亮的理论，它把这种失败归结为一个深刻的数据猜想，这个理论就是NP-完全性理论。定义：给定一个判定问题，如果存在一个算法，对任何一个答案为“是”的实例I。该算法首先给出一个猜想，该猜想规模不超过I的输入长度的某个多项式函数，且验证猜想的正确性仅需多项式时间，则称该问题属于NP类。定义：如果NP类中所有问题都可以多项式时间归约到NP类中某个问题x，则称x是NP-完全问题。定义：如果某优化问题x的判定问题是NP-完全的，则称问题x是NP-难的；如果x的判定问题是强NP-完全的，则称x是强NP-难的。

定义：若存在一个常数c，使得对于所有n>=0，都有|f(n)| <= c*|g(n)|，则称函数f(n)是o(g(n))。时间复杂度是o(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。不能够这样限制时间复杂度的算法被称为指数时间算法。例如：时间复杂度为o(nlog(n))、o(n^3)的算法都是多项式时间算法，时间复杂度为o(n^log(n))、o(n!)、o(2^n)的算法是指时间算法。一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并将这类问题的集合记为p，因此多项式时间可解问题就称为p类问题。一个问题如果没有找到多项式时间算法，那么直觉上它是“难解”的，但又往往无法证明多项式时间算法的不存在性。由于在寻找有效算法上的失败未必一定意味着这样的算法不存在，这就给理论工作者带来了一个难题：一方面证明一个问题不存在多项式时间算法是困难的，至今尚未给出；另一方面有越来越多的问题无法给出多项式时间算法。同时，理论工作者又渴望解决此难题。为此，在20世纪70年代提供了一个漂亮的理论，它把这种失败归结为一个深刻的数据猜想，这个理论就是np-完全性理论。定义：给定一个判定问题，如果存在一个算法，对任何一个答案为“是”的实例i。该算法首先给出一个猜想，该猜想规模不超过i的输入长度的某个多项式函数，且验证猜想的正确性仅需多项式时间，则称该问题属于np类。定义：如果np类中所有问题都可以多项式时间归约到np类中某个问题x，则称x是np-完全问题。定义：如果某优化问题x的判定问题是np-完全的，则称问题x是np-难的；如果x的判定问题是强np-完全的，则称x是强np-难的。

文章TAG：多项多项式多项式时间时间多项式时间