推 jameschou:我回在下面那篇囉~ 04/29 19:39
※ 引述《jameschou (DOG)》之銘言：
: ※ 引述《kiwidoit (橘子愛玉~>_^)》之銘言：
: : 題目如下:
: : line1 sum=0;
: : line2 for(i=1;i<n;i++)
: : line3 for(j=1;j<i*i;j++)
: : line4 if(i%j==0)
: : line5 for(k=0;k<j;k++)
: : line6 sum++;
: : line1執行一次
: : line2執行n+1次
: 應該是n次
: : line3開始我就不知道怎麼算了QAQ
: : 請問有神人知道line3~line6的執行次數各是多少?
: 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要怎麼算才好@@?
請各位幫忙解答一下> <" 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.123.221.96