推 kiwidoit:感謝 05/09 01:35
※ 引述《kiwidoit (橘子愛玉~>_^)》之銘言：
: ※ 引述《jameschou (DOG)》之銘言：
: : 應該是n次
: : line3~line6不能個別算吧
: : line2~line6應該一起看才對
: : 從line5來看
: : 每到一次line5的迴圈
: : 就要執行line6那行j次
: : line4其實我覺得應該是if(j%i==0)感覺比較有意義
: : 不然j比i大的時候i%j都不可能是0了
: : 不過就先照你打得這樣算吧
: : 所以line4只要看j是1到j是i的狀況即可
: : j若為i的因數就要執行line5
: : 也就是讓sum加上這個因數的值
: : 而最後sum的數目其實就是line6的執行次數了
: : 依照以上幾點來看
: : sum存的就是 1~(n-1)中每個數的所有正因數和
: : 但感覺沒辦法寫成一個固定的答案
: : 不知道有沒有更好的方法...
: 那如果line4 是if(j%i==0)的話，下面是我的算式
: 當line2的 i=1 i=2 i=3 i=4 ......
: 則line3的 j=X j=1~3 j=1~8 j=1~15 ......
: line4發生後j只剩 j=X j=2 j=3,6 j=4,8,12 ......
: for迴圈裡面的SUM會執行 0次 2次 3+6次 4+8+12次 ......
: 這樣它的Big-O要怎麼算才好@@?
: 請各位幫忙解答一下> <" 謝謝
如果line4是if(j%i==0)
代表j是i的倍數才會跑下面line5的for(k=0;k<j;k++)
也就是每當j為i的倍數時
sum就加上j (line5的k=0 ~ k=j-1 , 而事實上line5是執行j+1次)
因為i是1~n-1 , j是1~i^2-1
所以if那行會往下執行的是j=i,2i,3i,...,(i-1)i
n-1 i-1
因此sum = Σ Σ (j*i)
i=1 j=1
n-1 i-1
= Σ i*( Σ j)
i=1 j=1
n-1 i(i-1)
= Σ i*(--------)
i=1 2
n-1 n-1
=(1/2)*[ Σ (i^3) - Σ (i^2) ]
i=1 i=1
n(n-1) (n-1)(n)(2n-1)
=(1/2)*[ (--------)^2 - ---------------- ]
2 6
3n^4 - 10n^3 + 9n^2 - 2n
= ----------------------------
24
如果題目改成你現在這樣
那上面這個應該就是答案的通式了
如果是求big O 那就是 O(n^4)
我剛剛有稍微驗算一下n=1 ~ n=5
應該是沒錯
附上我用C測試的程式碼跟執行結果讓你參考
code:
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int n,sum,i,j,k;
while(1){
printf("n = ");
scanf("%d",&n);
sum=0;
for(i=1;i<n;i++)
for(j=1;j<i*i;j++)
if(j%i==0)
for(k=0;k<j;k++)
sum++;
printf("sum = %d\n\n",sum);
//system("pause");
}
return 0;
}
==============================================================================
執行結果:
n = 1
sum = 0
n = 2
sum = 0
n = 3
sum = 2
n = 4
sum = 11
n = 5
sum = 35
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.82