大家好，如果您还对多项式时间算法不太了解，没有关系，今天就由本站为大家分享多项式时间算法的知识，包括既约多项式什么时候学的问题都会给大家分析到，还望可以解决大家的问题，下面我们就开始吧！
本文目录
一、什么是多项式时间
1、就是问题需要的时间（复杂度）与问题的规模之间是多项式关系。
2、举个例子，现在从n阶图中找两点的最短路径，复杂度为n^2级别（即O(n^2)，O是大写欧），而n^2对于n是多项式（单项式当然也算），这就称为是多项式复杂度，或者多项式时间，其中问题（算法）的规模是n。如果某一个算法的规模是n，但是复杂度比如是2^n，写不成n的多项式，那就不是多项式时间。
二、什么叫多项式时间算法
1、多项式时间在决定型机器上是最小的复杂度类别，且在机器模型改变时依旧强韧，且也是可在副程式组合过程中保持封闭的类别。
2、数学家有时把“比多项式时间长的算法”视为快速计算，相对应的是超多项式时间，表示任何多项式时间的输入数目只要够大，超多项式时间所需的解题时间终究会大大超过任何多项式时间的问题。
3、多项式时间在计算复杂度理论中，指的是一个问题的计算时间不大于问题大小的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。
4、多项式时间在决定型机器上是最小的复杂度类别，且在机器模型改变时依旧强韧，且也是可在副程式组合过程中保持封闭的类别。
5、强多项式时间指的是此问题的运算时间不因输入资料的数字大小而变动，而是依照输入资料的结构复杂度。
三、什么是伪多项式时间算法
1、想要理解“伪多项式时间”，我们需要先给出“多项式时间”的一个清楚的定义。
2、对于“多项式时间”，我们的直观概念是时间复杂度,其中是一常数。比如，选择排序的时间复杂度是，是多项式时间；暴力解决TSP问题的时间复杂度是，不是多项式时间。我们称这种时间复杂度为“传统时间复杂度”。
3、我们通常认为传统时间复杂度中的变量表示数据的输入规模。比如，选择排序中，指待排序数组中元素的个数；TSP问题中表示图中节点的数量。但是，这些所谓的输入规模，仅仅是直观的定义，并不足够严谨。为了标准化这些，在计算标准时间复杂度时，我们给出了输入规模的标准定义：
4、一个问题的输入规模是保存输入数据所需要的bit位数。
5、比如，如果排序算法的输入是一个32-bit整数数组，那么输入规模就是，是指数组中元素的个数。对于一个带有个节点、条边的图，需要的bit位数就是。
6、了解了输入规模的定义，我们来看“多项式时间”的标准定义：
7、对于一个问题，在输入规模为x的情况下，如果一个算法能够在O()时间内解决此问题，则我们称此算法是多项式时间的，其中为一常数。
8、当我们处理一些图论、链表、数组、树等问题时，这个标准定义下的多项式时间和我们传统的多项式时间相差无几。比如，用选择排序对元素个数为的数组进行排序时，传统时间复杂度为。输入规模，因此，得到的标准时间复杂度是，仍然是多项式时间。
9、类似的，假设在带有个节点、条边的图中做DFS(深度优先搜索)，传统时间复杂度为。数据规模，因此，标准时间复杂度是，仍是多项式时间的。
10、然而，当我们处理一些与数论有关的问题时，事情就不太乐观了。现在我们来讨论判断一个整数是否为素数的算法，下面是一个简单的算法：
11、显然，这个算法在传统时间复杂度计算 *** 中是多项式时间的。我们不妨认为它的传统时间复杂度是。然后我们再来分析这个问题的输入规模，可能有的同学会说，对于32-bit整数，这个输入规模不就是32吗？这话虽然没错，但是因为在这个问题中，输入规模完全依赖于的大小，所以的范围不再限制在32-bit整数的范围内，而是要探讨当更大时对数据规模的影响。我们知道，保存一个整数所需要的bit位数，因此，在标准的时间复杂度中，此算法的复杂度变为了!这已经不再是多项式时间，而是一个指数时间。
12、我们可以从下面这个例子中直观感受一下这种指数时间的增长速度：
13、我们记指数时间复杂度算法运行时间为T。
14、然后，我们在二进制串后面仅仅增加一位：
15、这时，算法运行时间会变为2T(至少)！因此，我们仅仅增加几个bit就会使得算法运行时间成倍成倍的增长。
四、多项式算法
定义：若存在一个常数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-难的。
这个其实很简单，需要3个数组（暂时考虑int数组），长度都是10，分别保存多项式1、2和计算结果。初始化为全0。输入就按照你的假设吧。输入后三个数组分别为：
多项式1：[7, 0,-5, 2, 0, 0, 0, 0, 0, 0]（x的0次幂系数是7，x的1次幂系数是2，以此类推，下同）
多项式2：[-8, 1, 3, 0, 0, 0, 0, 0, 0, 0]
计算结果：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]（还没算呢，当然都是0）
加法减法很好算，不赘述。乘法怎么算呢，你按照真实的数学计算步骤推一遍就知道了，你会把3x2、x、-8分别乘以2x3-5x2+7，最后把结果加起来。转换到程序中，就是把若干个数组加起来：
[-56, 0, 40,-16, 0, 0, 0, 0, 0, 0]
[0, 7, 0,-5, 2, 0, 0, 0, 0, 0]
[0, 0, 21, 0,-15, 6, 0, 0, 0, 0]
至于提高水平，这个题目出得不好，因为多项式相除结果不唯一。比如说2x2+ 1除以x2+ 1，你可以说2x2+ 1= 2(x2+ 1)- 1，也可以说2x2+ 1= 1(x2+ 1)+ x2。这样的题目数学上就意义不大，用程序去实现也达不到锻炼水平的作用。也许我理解有误？
给定两个多项式，实现两个多项式相加算法。用c语言编程
输入data2的时候，鼎看你for里面是j，scanf里面是i，读不进去
scanf("%d%d",&data2[i].a,&data2[i].b);
printf("%d%d\n",data[t].a,data[t].b);
i是步过值，结果用t输出，怎么也得用data[i].a吧
我刚做好的课程设计，得了个A+，免费给你了，包你满意，几乎没有漏洞！头文件#include#include#include定义多项式的项 typedef struct Polynomial{ float coef; int expn; struct Polynomial*next;}*Polyn,Polynomial; void Insert(Polyn p,Polyn h){ if(p->coef==0) free(p);系数为0的话释放结点 else{ Polyn q1,q2; q1=h; q2=h->next; while(q2&&p->expn expn){查找插入位置 q1=q2; q2=q2->next;} if(q2&&p->expn==q2->expn){将指数相同相合并 q2->coef+=p->coef; free(p); if(!q2->coef){系数为0的话释放结点 q1->next=q2->next; free(q2);}} else{指数为新时将结点插入 p->next=q2; q1->next=p;}}} Polyn CreatePolyn(Polyn head,int m){建立一个头指针为head、项数为m的一元多项式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i coef,&p->expn); Insert(p,head);调用Insert函数插入结点} return head;} void DestroyPolyn(Polyn p){销毁多项式p Polyn q1,q2; q1=p->next; q2=q1->next; while(q1->next){ free(q1); q1=q2; q2=q2->next;}} void PrintPolyn(Polyn P){ Polyn q=P->next; int flag=1;项数计数器 if(!q){若多项式为空，输出0 putchar('0'); printf("\n"); return;} while(q){ if(q->coef>0&&flag!=1) putchar('+');系数大于0且不是之一项 if(q->coef!=1&&q->coef!=-1){系数非1或-1......>>
多项式运算法则：有括号先去括号，然后合并同类项。
在while(cin>>n>>x)这个主循环中，每运行一次sum就得清一次零……
#include#include using namespace std;int main(void){ int a[9],n,i,j; double x,sum=0,sum1=1; while(cin>>n>>x){ for(i=n;i>=0;i--) cin>>a[i]; n=n+1; while(n--){ sum=0;清零sum for(j=1;j<=n;j++) sum1*=x; sum+=a[n]*sum1; sum1=1;} cout<
五、什么是概率多项式时间
1、概率多项式时间（Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。
2、数学家有时把“比多项式时间长的算法”视为快速计算，相对应的是超多项式时间，表示任何多项式时间的输入数目只要够大，超多项式时间所需的解题时间终究会大大超过任何多项式时间的问题。指数时间（Exponential time）就是一例。
3、超多项式时间：O(c^f(n))，其中c为大于1的常数，f(n)大于常数，小于线性。
4、可以在决定型依序机器上（例如图灵机）以多项式时间解决的决定性问题，其属于的复杂度类被称为P。可以在多项式时间验证答案的非决定性问题称为NP。而NP也是可以在非确定型图灵机以多项式时间解决的问题（NP两字为Non-deterministic Polynomial的缩写）。
关于多项式时间算法的内容到此结束，希望对大家有所帮助。
