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

看板Grad-ProbAsk作者 (GraphicProcessUnit)時間16年前 (2010/02/25 01:31), 編輯推噓3(3推 0噓 8→)
留言11則, 4人參與, 最新討論串1/1
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
推
02/25 01:42, , 1F
union是根據兩個SET的elements個數大小來選擇哪一tree的樹
02/25 01:42, 1F
→
02/25 01:44, , 2F
跟做為整體的樹根，較小的那個root會指向較大的root
02/25 01:44, 2F
→
02/25 01:45, , 3F
FIND(i)是指搜尋路徑（由I到root)所經過的node的parent指
02/25 01:45, 3F
→
02/25 01:46, , 4F
標改成指向root，用來減少find的所需時間
02/25 01:46, 4F
→
02/25 01:47, , 5F
union:O(1) Find:O(logn)
02/25 01:47, 5F
→
02/25 01:53, , 6F
17題第一題是ture 第二題應該是false...如果仔細去找的話
02/25 01:53, 6F
→
02/25 01:56, , 7F
應該要O（n） 第3.4是O（logn）第5題應該是O（U+Flogn）
02/25 01:56, 7F
→
02/25 08:07, , 8F
謝謝!!!!!!!!!!
02/25 08:07, 8F
推
02/25 09:05, , 9F
4.O(n) 因為最差也才n
02/25 09:05, 9F
→
02/25 09:05, , 10F
且 union and find 有很多種組合
02/25 09:05, 10F
推
02/26 12:22, , 11F
星期一再跟你解說 XD
02/26 12:22, 11F
‣ 更多 gpu 的文章
文章代碼(AID): #1BXM9j-- (Grad-ProbAsk)