Re: [理工] 資料結構消失

看板Grad-ProbAsk作者時間8年前 (2016/03/22 20:26), 編輯推噓1(1推 0噓 6→)
留言7則, 2人參與, 最新討論串9/17 (看更多)
※ 引述《gsmzxcvbnm ()》之銘言： : 洪逸的資料結構某題答案與其它本不同， 洪逸的版本我也看不太懂 : 洪逸 : http://i.imgur.com/9A0xbL0.jpg
: 高點 : http://i.imgur.com/E66FgFz.jpg
我還是不知道n-ki=1是怎麼來的耶，n-ki應該是第k項吧？那怎麼會等於1? 所以效能是把所有k加起來?我完全不懂啊 而且我一開始的想法是 x=n-1 x=n-2 x=n-3 . . . . x=n-n T(n)=n^2-(n+1)n/2=O(n^2) 這樣想好像很白痴 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.23.159 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1458649600.A.EA4.html
推
03/22 23:51, , 1F
精確來說應該是 當x = n - ki = c, 為第k個while loop
03/22 23:51, 1F
→
03/22 23:52, , 2F
其中 0 < c < i
03/22 23:52, 2F
→
03/22 23:53, , 3F
(那個說明是在講第k+1個loop時, x<=0)
03/22 23:53, 3F
→
03/22 23:54, , 4F
後面再對 i = 1...n,個別狀況加總
03/22 23:54, 4F
→
03/22 23:55, , 5F
想成T(n) = t(1) + t(2) + ... + t(i) + ... + t(n)
03/22 23:55, 5F
→
03/22 23:57, , 6F
t(i) 即為 k次 loop的時間, 又 k = (n-c)/i , 答案可求
03/22 23:57, 6F
→
03/23 08:21, , 7F
嗯嗯，謝謝
03/23 08:21, 7F
‣ 更多 gsmzxcvbnm 的文章
文章代碼(AID): #1MyJe0wa (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 9 之 17 篇)：
排序： 最舊先 | 最新先 | 留言數
理工
4
29
[理工] 資料結構 資料結構
n791116
10年前, 12/30
在新視窗開啟完整討論串 (共17篇)
‣ 更多 gsmzxcvbnm 的文章
文章代碼(AID): #1MyJe0wa (Grad-ProbAsk)