2

我应该使用积分获得算法的下限和上限,但我不明白该怎么做。我知道基本的积分原理,但我不知道如何从算法中找出积分。

问题:

  • 我的第一个 for 循环从 i = 5n ---> 开始,然后到 6n 立方,
    • 里面的下一个将从 j=5 ---> 开始,然后到 i,
      • 那么最后的下一个 for 循环将从 k=j 开始并到 i。

自然,我的第一步是把它变成 3 个总和。因此,我设置了 3 个汇总,我想要做的是尽可能将这些汇总简化为一个汇总。这样,如果我的求和右侧有一些变量,我现在可以取积分。

就我用于积分的范围而言,从 Cormen、Leiserson 等的算法介绍中,您可以通过积分进行近似。

积分的性质

  • 对于上限,您的积分界限可能是:上限 n+1,下限 m。
  • 对于下限,您的积分界限可能是:上限 n,下限 m-1。

如果可能,我想知道如何将我的三个总和简化为一个。如果事情是一个总和,我可以开始取积分并自己从那里开始。

这是非常粗糙的伪代码,但我尽我所能让它看起来与实际代码相似。

for(i = 5n; i<6n^3; i++)
{
    for(j =5; j<i; j++)
    {
        for(k=j; k < i; k++)
        {
            i - j + k;
        }
    }
}
4

1 回答 1

2

让任何一个int(i,j,f)int(x=i,j,f(x))∫(x=i,j,f(x))表示 x 的定积分f(x)范围从 i 到 j。如果f(x)是当 x 具有特定值时(由程序)完成的工作量,并且如果 f 是单调递增函数,那么正如您在问题中指出的那样,int(m,n+1,f)是工作的上限和 int(m+1,n,f)下限在 x 取值时完成m...n。在下文中,我会说这int(m,n,f)近似于工作,您可以+1在适当的地方添加术语以获得上限和下限。注意,6n^3-1 代表 6*(n^3)-1,5n 代表 5*n,等等。

近似的工作是:
int(i=5n, 6n^3-1, u(i))
where u(i)is
int(j=5, i-1, v(i,j)) where v(i,j)is
int(k=j, i-1, w(k)) where w(k)is 1. 下面我们使用函数 p、q、r 代表不定积分,而 C 代表积分常数,抵消定积分。

r(x) = ∫1dx = x + C.
现在v(i,j) = ∫(k=j, i-1, 1) = r(i-1)-r(j) = i-1-j

q(x,i) = ∫(i-1-x)dx = x*(i-1)-x*x/2 + C.
现在u(i) = ∫(j=5, i-1, i-1-j) = q(i-1,i)-q(5,i)
这是 中的一些二次方i。您将需要计算出上限和下限案例的详细信息。

p(x) = ∫u(x)dx = ∫(q(x-1,x)-q(5,x)),它是 x 中的某个立方。总体结果是
p(6n^3-1)-p(5n)
,您将需要再次确定细节。但请注意,当6n^3-1在 p(x) 中替换 x 时,顺序将是(6n^3-1)^3,即 O(n^9),因此您应该期望上界和下界表达式为 O(n^9)。请注意,您还可以通过检查循环来查看 O(n^9) 顺序:在for(i=5n; i<6n^3; i++)中,我将平均大约3n^3. 在for(j =5; j<i; j++)中,j 的平均值约为 i/2,或 n^3 的一些小倍数。在for(k=j; k < i; k++)中,k-j也将平均 n^3 的小倍数。因此,表达式i-j+k将被计算 n^3*n^3*n^3 或 n^9 次的小倍数。

于 2012-10-12T07:14:05.500 回答