Re: [理工] 100成大資工 DS＆Algo(資結)

看板Grad-ProbAsk作者Byzantin (拜占庭)時間14年前 (2012/01/12 21:54)推噓10(10推 0噓 15→)

留言25則, 5人參與討論串2/3 (看更多)

※ 引述《genius945 (添財)》之銘言： : http://0rz.tw/SkLcE 題目 : 看板上好像只有去年考完有人討論... : 一堆都不會...整個亂寫 : 答案 PO上來請各位幫忙修正&指導 = = : 1. : (a)Binary search tree 我覺得是AVL-tree : (b)B tree of order 3 (2-3 tree) : (c)Max Heap(binary) : 2. : (a) 不會...瞎寫了一個code後來發覺不是O(lgn) : 所以(b)也不甭提了... : 3. : 這題好難,我幾乎沒一個是確定的都亂矇 : a-6 : b-2 : c-9 : d-7 我也都不太確定但只有(d)跟你不同我選(1) : e-4 : f-3 : 4.θ(nloglogn) : 5. : 這題應該會有不同答案吧 : 給左右給0或1或是合併次序 : 我做的是 : a:01 : b:0000 : c:001 : d:101 : e:11 : f:0001 : g:100 : 6. : 不會 : 一開始看到複雜度想說先做kruskal's algo O(V^2logV) : 再搭個BFS之類的 : 但後來想想有邊在MST並不能保證此邊是這兩點的最短距離= = : 我就掰了 Orz 應是Johnson's algorithm : 7. : 我的想法是 : step1.做類似counting sort的動作,計算1~k各有幾個 : 假設這n個int存在int[n] : 建count[k],初值皆為0 : for i = 1 to n : count[int[i]]++ : O(n) : step2.建立一個sum[k],存count[1]+....+count[i]之sum : sum[1]=count[1] : for i = 2 to k : sum[i]=sum[i-1]+count[i] : O(k) : 時間複雜度為O(n+k) : 若要知道多少個int在range a~b : 則只要 return (sum[b]-sum[a-1])即可故為O(1) 其餘沒回覆的，你有寫的我的答案都相同，你不會的我也不會囧 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.169.104.205

推

justbelieve

01/12 22:01, , 1^F

01/12 22:01, 1^F

※ 編輯: Byzantin 來自: 118.169.104.205 (01/12 22:02)

推

genius945

01/12 22:04, , 2^F

01/12 22:04, 2^F

→

genius945

01/12 22:06, , 3^F