算法边界分析和使用积分

Question

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

问题:

• 我的第一个 for 循环从 i = 5n 开始 ---> 到 6n 的立方，
  • 里面的下一个将从 j=5 开始 ---> 到 i，
    • 那么最后的 next 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;
        }
    }
}

Answer 1

让int(i,j,f)中的任何一个或 int(x=i,j,f(x))或 ∫(x=i,j,f(x))表示 f(x) 的定积分因为 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))
其中 u(i)是
int(j=5, i-1, v(i,j))其中 v(i,j)是
int(k=j, i-1, w(k))其中 w(k)为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 次的小倍数。