作者jameschou (DOG)
看板Grad-ProbAsk
標題Re: [理工] [資結]analysis of running time
時間Thu Apr 28 12:03:33 2011
※ 引述《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)中每個數的所有正因數和
但感覺沒辦法寫成一個固定的答案
不知道有沒有更好的方法...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.82
※ 編輯: jameschou 來自: 140.113.139.82 (04/28 12:04)
推 kiwidoit:感謝解答QAQ" 04/29 00:53
推 roadeat:line 2應該是(n-1)次 04/29 17:20
→ roadeat:line 3、4 應該是 ((n-1)*((n-1)-1)*(2*(n-1)+1))/6 次 04/29 17:21
→ roadeat:Σi^2的公式 (n*(n+1)*(2n+1))/6 不知道有沒有記錯@@ 04/29 17:22
→ roadeat:line 5 6 我也覺得是一個變動的次數...如果是求Big-O 04/29 17:23
→ roadeat:應該就可以估算了 04/29 17:23
→ roadeat:我line 3 4中間應該是 ((n-1)+1) 打錯了 04/29 17:24
推 rayway30419:用程式跑也看不出規律說QQ 04/29 17:50
→ jameschou:line2是n次 因為i=n還是要跑那一行判斷 04/29 18:24
→ roadeat:3Q 04/29 20:20