[理工] 資料結構

看板Grad-ProbAsk作者 (阿湯)時間9年前 (2016/04/04 13:32), 9年前編輯推噓2(2推 0噓 11→)
留言13則, 4人參與, 最新討論串11/17 (看更多)
想問三顆星那題，要怎麼算，而且跟例3為什麼等同？http://i.imgur.com/R1TqTWb.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.13.225.71 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1459747921.A.CCD.html ※ 編輯: h42318 (39.13.225.71), 04/04/2016 13:32:37
→
04/04 15:32, , 1F
另解是可以用離散的觀點看, 1到n相當於有n個數, 問題
04/04 15:32, 1F
→
04/04 15:32, , 2F
可看作n個數中取三個, 且三數中有大小關係的方法數,
04/04 15:32, 2F
→
04/04 15:32, , 3F
上下兩題就只是三數的代數表示換了下，原本是n數中
04/04 15:32, 3F
→
04/04 15:32, , 4F
取i,j,k三數且1<=k<=j<=i<=n，改成1<=i<=j<=k<=n，方
04/04 15:32, 4F
→
04/04 15:32, , 5F
法數應不變
04/04 15:32, 5F
推
04/04 15:49, , 6F
Note部分, 每個迴圈一共算n次, Θ(n^3)
04/04 15:49, 6F
→
04/04 15:51, , 7F
例三, 實際算n^3/6, 也在Θ(n^3)底下
04/04 15:51, 7F
推
04/05 01:35, , 8F
用兩層舉例,假設外層都是i=1 to 10
04/05 01:35, 8F
→
04/05 01:35, , 9F
內層(1)j=1 to i跟(2) j=i to n差別為(1)i=1,j跑1次 i=
04/05 01:35, 9F
→
04/05 01:35, , 10F
2,j跑2次=>1+2+...+10=55次
04/05 01:35, 10F
→
04/05 01:35, , 11F
(2)i=1,j跑10次 i=2,j跑9次=>10+9+...+1=55次
04/05 01:35, 11F
→
04/05 01:35, , 12F
所以一樣
04/05 01:35, 12F
→
04/05 22:42, , 13F
懂了！感謝
04/05 22:42, 13F
‣ 更多 h42318 的文章
文章代碼(AID): #1N0VnHpD (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 11 之 17 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共17篇)
‣ 更多 h42318 的文章
文章代碼(AID): #1N0VnHpD (Grad-ProbAsk)