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

[APE36 (PT鄉民)]

for (i=1; i<=n; i++) {
   j=i+1;
  do {
    x=x+1;
  } while (j++ <= n);
}

請問，關於x = x + 1 的執行次數?在考試時，通常都怎麼整理的?

感覺老師，都說要用公式套
請益有人能幫解惑一下嗎??


--
                       Ｑ：高雄市的飆車族到底多不多？

　　　　　Ａ：飆車族不多阿，只有一兩台，前面五十台是不敢停下來，怕被砍

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.124.53
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1431681746.A.7C8.html
推 popular10347: n*[(n+1)*n/2]
推 popular10347: 外層迴圈對x有影響執行n次,內層迴圈你從i=1會執行n
→ popular10347: 次,i=2執行n-1次...i=n執行1次
推 easion0317: 問一下 迴圈跑到最後是不是要加一 因為判斷失敗要跳出
→ easion0317: 算一次
→ popular10347: 你現在問的不是x執行次數?
→ popular10347: 然後通常不知道怎麼看我會先代個n=5之類的數字,來緩
→ popular10347: 解恐懼
→ popular10347: 如果是看外層for迴圈就是執行n+1次
→ ken52011219: 小弟不才While(j++<=n)這成是不是永遠j>n嗎 ??
推 fightforlive: 因為是do...while 所以一定會執行一次,下次要執行才
→ fightforlive: 會在while裡判斷條件,所以除了第一次執行,第二次之
→ fightforlive: 後會在j++後然後執行; j++<=n會先判斷j<=n然後才
→ fightforlive: j=j+1 所以如果j=1, n=2, 會執行j=1,j=2,j=3
→ fightforlive: 所以在while裡有可能j>n