2

積分を使ってアルゴリズムの下限と上限を取得することになっていますが、その方法がわかりません。私は基本的な積分原理を知っていますが、アルゴリズムから積分を理解する方法がわかりません。

問題：

  • 私の最初のforループはi=5n --->で始まり、6nの3乗になります。
    • 次のものはj=5 --->で始まり、iに行きます。
      • 次に、最後の次のforループはk = jで始まり、iに進みます。

当然、私の最初のステップは、これを3つの合計に変換することでした。だから私は3つの合計を設定しました。私がやりたいのは、可能であればこれらを1つの合計に単純化することです。そうすれば、合計の右側にいくつかの変数がある場合、積分を取ることができます。

積分に使用している範囲に関しては、Cormen、Leisersonなどによるアルゴリズムの概要から、積分による近似を行うことができます。

積分の性質：

  • 上限の場合、積分の境界は次のようになります。上限n + 1、下限m。
  • 下限の場合、積分の範囲は次のようになります。上限n、下限m-1。

可能であれば、3つの合計を1つに単純化する方法を知りたいです。物事が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

xの範囲がiからjであるため、int(i,j,f)またはのいずれint(x=i,j,f(x))か∫(x=i,j,f(x))をの定積分を示します。f(x)xが特定の値を持っているときに（プログラムによって）実行される作業量であり、 ff(x)が単調増加関数である場合、質問で指摘するように、は作業の上限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などを表します。

おおよその作業は次のとおりです 。whereiswhereis where
int(i=5n, 6n^3-1, u(i))
is u(i)1以下
int(j=5, i-1, v(i,j)) でv(i,j)は、関数p、q、rを使用して不定積分を表し、Cを使用して定積分を相殺する積分定数を表します。
int(k=j, i-1, w(k))w(k)

しましょう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)
は、の2次式ですi。上限と下限の場合の詳細を理解する必要があります。

、 xp(x) = ∫u(x)dx = ∫(q(x-1,x)-q(5,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 に答える