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 回答