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

看板Grad-ProbAsk作者genius945 (添財)時間14年前 (2012/01/12 21:45)推噓3(3推 0噓 2→)

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

http://0rz.tw/SkLcE 題目看板上好像只有去年考完有人討論... 一堆都不會...整個亂寫答案 PO上來請各位幫忙修正&指導 = = 1. (a)AVL 感謝版友 (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-1(版友指正XD) 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 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: 218.173.192.163

推

FY4

01/12 22:01, , 1^F

01/12 22:01, 1^F

→

genius945

01/12 22:06, , 2^F

01/12 22:06, 2^F

※ 編輯: genius945 來自: 218.173.192.163 (01/12 22:07) ※ 編輯: genius945 來自: 218.173.192.163 (01/12 22:08)

推

pikachu123

01/12 22:30, , 3^F