[理工] 資節 時間複雜度分析

作者: APE36 (PT鄉民)   2015-05-15 17:22:24
for (i=1; i<=n; i++) {
j=i+1;
do {
x=x+1;
} while (j++ <= n);
}
請問,關於x = x + 1 的執行次數?在考試時,通常都怎麼整理的?
感覺老師,都說要用公式套
請益有人能幫解惑一下嗎??
作者: popular10347 (popular)   2015-05-15 21:13:00
n*[(n+1)*n/2]外層迴圈對x有影響執行n次,內層迴圈你從i=1會執行n次,i=2執行n-1次...i=n執行1次
作者: easion0317 (仲夏螢火蟲)   2015-05-16 06:20:00
問一下 迴圈跑到最後是不是要加一 因為判斷失敗要跳出算一次
作者: popular10347 (popular)   2015-05-16 11:32:00
你現在問的不是x執行次數?然後通常不知道怎麼看我會先代個n=5之類的數字,來緩解恐懼如果是看外層for迴圈就是執行n+1次
作者: ken52011219 (呱)   2015-05-25 22:57:00
小弟不才While(j++<=n)這成是不是永遠j>n嗎 ??
作者: fightforlive (學歷無用論是屁)   2015-05-30 20:10:00
因為是do...while 所以一定會執行一次,下次要執行才會在while裡判斷條件,所以除了第一次執行,第二次之後會在j++後然後執行; j++<=n會先判斷j<=n然後才j=j+1 所以如果j=1, n=2, 會執行j=1,j=2,j=3所以在while裡有可能j>n

Links booklink

Contact Us: admin [ a t ] ucptt.com