[理工] [資結] 98台大電機資結的幾個問題

[gpu (GraphicProcessUnit)]

http://www.lib.ntu.edu.tw/exam/graduate/98/98398.pdf

第17題

什麼是"union-and-find"阿?

還有第11題

open address和close address是什麼阿?

感覺念書的時候好像沒有念到這些概念~"~

但是好像很重要的樣子~"~

先謝謝嚕~

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 163.25.118.136
推 tureday:union是根據兩個SET的elements個數大小來選擇哪一tree的樹
→ tureday:跟做為整體的樹根，較小的那個root會指向較大的root
→ tureday:FIND(i)是指搜尋路徑（由I到root)所經過的node的parent指
→ tureday:標改成指向root，用來減少find的所需時間
→ tureday:union:O(1) Find:O(logn)
→ tureday:17題第一題是ture 第二題應該是false...如果仔細去找的話
→ tureday:應該要O（n）  第3.4是O（logn）第5題應該是O（U+Flogn）
→ gpu:謝謝!!!!!!!!!!
推 davidmax1: 4.O(n) 因為最差也才n
→ davidmax1:且 union and find 有很多種組合
推 enozs:星期一再跟你解說 XD