算法結合分析，並使用積分

我應該得到一個下限和上限使用積分的alogrithm的，但我不知道該怎麼做。我知道基本的整合原則，但我不知道如何從算法中找出積分。算法結合分析，並使用積分

問題：

我的第一個for循環開始於I = 5N --->並進入到6n立方，
- 內的下一個將在J = 5被啓動 - - >和去I，
  - 然後for循環的最後將下在k = J值開始到我。

當然，我的第一步是把它變成3個求和。所以我有3個總結，我想要做的就是儘可能將這些簡化成簡單的總和。這樣，如果我的總和權利有一些變數，我現在可以拿積分。

在由Cormen，Leiserson等，您可以通過積分做近似我用我的積分界限，從算法導論的條款。

積分的性質：

對於上界的積分的範圍可以爲：上限N + 1，下界米。
對於下限，你的積分的界限可以是：上界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; 
     } 
    } 
}

來源

2012-10-11 Tastybrownies

請仔細檢查，目前的解釋不夠豐富。從i = 5n到「6n立方體」的循環在不知道「i」在迭代之間如何表現的情況下並不是什麼都不說。你可以發佈代碼示例嗎？ – amit

好吧，我盡我所能讓它看起來像實際的代碼。所有這些現在都非常混亂。 – Tastybrownies

由於前幾個段落中的代碼而不是文本格式，您的帖子很難閱讀。不要使用這麼多空格縮進普通文本，以至於打開代碼格式。請編輯您的問題並修復它 –

讓任何的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。
Now 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)
並且您將需要制定詳細信息。但是請注意，當p（x）中的6n^3-1代替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-12 07:14:05

非常感謝你！我相信這是正確的。 – Tastybrownies

算法結合分析，並使用積分

回答

相關問題