1.介绍

在数学中,多项式是一个表达式,包含一个或多个变量的幂乘以系数。一个单变量多项式,x,常系数为:a_0 + a_1x + a_2x ^ 2 +…+现代x ^ {n} {n} + a_nx ^ n。我们称每一项为,a_nx ^ n,一个术语。如果两项幂相同,我们称它们为类项。

在本教程中,我们将展示如何使用链表数据结构对两个多项式进行相加和相乘。

2.用链表表示一个多项式

我们可以用链表表示一个多项式。在链表中,每个节点有两个数据字段:系数和功率。因此,每个节点代表一个多项式的项。例如,我们可以表示多项式用2 + 5 x ^ 2使用链表:

我们可以对链表排序O (n \ log n)时间,n是链表节点的总数。在本教程中,我们将假定链表是根据算法的简单性来排序的。

3.添加两个多项式

将两个多项式相加,我们可以将相似项的系数相加,得到一个新的多项式链表。例如,我们可以用两个喜欢的列表来表示多项式用2 + 5 x ^ 21 + 2 x - 3 x ^ 3:

当我们将它们加在一起时,我们可以将类似的项分组并生成结果3  -  2x ^ 2 + 5x ^ 2  -  3x ^ 3:

因为两个链表都是按幂排序的,所以我们可以使用一个双指针方法来合并两个已排序的链表:

呈现由QuickLaTeX.com

在这个算法中,我们首先创建两个指针,p1p2,到头指针的两个输入多项式。然后,我们根据这两个指针的幂生成新的多项式节点。有三种情况:

  1. p1的力量大于p2在本例中,我们添加了一个新节点p1的功率和系数。同时,我们将p1到下一个节点。
  2. p2的力量大于p1在本例中,我们添加了一个新节点p2的功率和系数。同时,我们将p2到下一个节点。
  3. p1p2在这种情况下,新的系数是p1的系数和p2的系数。如果新的系数不是0,我们将一个具有相同功率和新系数的新节点。此外,我们搬家p1p2到下一个节点。

在此之后,继续添加来自的剩余节点p1p2直到我们完成所有节点的计算。

附加函数可以基于输入创建新的链表节点权力系数。此外,它将新节点附加到尾巴节点,并返回新的尾巴节点:

呈现由QuickLaTeX.com

这个算法只遍历每个链表节点一次。因此,总体运行时间为O (n + m),在那里n米为两个输入多项式的项数。

4.用两个多项式

要使两个多项式相乘,我们首先可以将一个多项式的每一项乘以另一个多项式。假设两个多项式有n米条款。这个过程将创建一个多项式与n \乘以m条款。

例如,在我们相乘之后用2 + 5 x ^ 21 + 2 x - 3 x ^ 3,我们可以得到一个链表:

这个链表包含生成最终结果所需的所有术语。然而,它不是按权力来排序的。此外,它还包含具有相似项的重复节点。要生成最终的链表,我们首先可以合并排序基于每个节点功率的链表:

排序之后,类似的术语节点被分组在一起。然后,我们可以合并每一组相似项,得到最终的乘法结果:

我们可以用一个算法来描述这些步骤:

呈现由QuickLaTeX.com

在该算法中,我们首先使用嵌套而将两个多项式中的所有项对相乘。这需要O (nm)时间,n米为两个输入多项式的项数。同样,这个过程创建一个链表n \乘以m节点。

然后,我们合并排序链表基于每个节点的功率。这个过程需要O (nm \ log (nm))时间。

在我们对链表排序之后,我们可以使用一个两个指针的方法来合并类似的术语:

呈现由QuickLaTeX.com

在这种方法中,我们使用一个指针作为类似术语组的开始,使用另一个指针遍历同一组中的类似术语。每次我们找到一个类似项,我们把它的系数加到开始的类似项节点上。一旦我们完成了一个类似的术语组,我们将开始指针移到下一个组,并重复相同的过程来合并类似的术语。此进程的运行时间为O (nm)因为我们需要去拜访n \乘以m节点。

总的来说,运行时间是O(nm) + O(nm\log (nm)) + O(nm) = O(nm\log (nm))

5.结论

在本教程中,我们展示了如何用链表数据结构表示多项式。此外,我们还展示了两种算法来相加和相乘多项式的两个链表表示。

客人
0评论
内联反馈
查看所有评论