Re: [理工] [資結]analysis of running time
※ 引述《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)
推
04/29 00:53, , 1F
04/29 00:53, 1F
推
04/29 17:20, , 2F
04/29 17:20, 2F
→
04/29 17:21, , 3F
04/29 17:21, 3F
→
04/29 17:22, , 4F
04/29 17:22, 4F
→
04/29 17:23, , 5F
04/29 17:23, 5F
→
04/29 17:23, , 6F
04/29 17:23, 6F
→
04/29 17:24, , 7F
04/29 17:24, 7F
推
04/29 17:50, , 8F
04/29 17:50, 8F
→
04/29 18:24, , 9F
04/29 18:24, 9F
→
04/29 20:20, , 10F
04/29 20:20, 10F
→
09/11 14:23, , 11F
09/11 14:23, 11F
討論串 (同標題文章)