[理工] 資結 binary search

看板Grad-ProbAsk作者 (蜜蜂P助)時間5年前 (2018/10/25 12:00), 編輯推噓4(4推 0噓 20→)
留言24則, 4人參與, 5年前最新討論串1/1
https://i.imgur.com/uB8iexF.jpg
請問這題的 1 3 4 1。 duplicative keys 是指說像是兩個重複的 5 出現之情況嗎？不太理解 primary keys 的意思 3。ISAM 好像是資料庫的內容？我有上網找了一下介紹，但沒看到比較重點的部分，這 部分不知道有什麼區別 4。資料量少不利，是因為 linear search 的 algorithm 步驟比較少（比較簡單）之 故？ 謝謝！！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.200.53.105 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1540440041.A.A38.html
推
10/25 17:29, 5年前 , 1F
4的話 BS還要先排序過 所以資料筆數少時不見得比LS
10/25 17:29, 1F
→
10/25 17:29, 5年前 , 2F
好
10/25 17:29, 2F
→
10/26 04:03, 5年前 , 3F
1.keys指的是資料庫中具有區分性的資料，假如是學生名
10/26 04:03, 3F
→
10/26 04:04, 5年前 , 4F
單，那姓名、學號、住址、...都可能是key
10/26 04:04, 4F
→
10/26 04:05, 5年前 , 5F
Primary key是實際被選出來當作代表的那一欄(或者數欄)
10/26 04:05, 5F
→
10/26 04:06, 5年前 , 6F
因為需要區分性，所以不希望它裡面有重複的值
10/26 04:06, 6F
→
10/26 04:06, 5年前 , 7F
但這題問的事情是，如果有重複的，那BS還可以用嗎？
10/26 04:06, 7F
→
10/26 04:07, 5年前 , 8F
會這樣問，是因為有不能用的狀況，也就是Hash Table
10/26 04:07, 8F
→
10/26 04:09, 5年前 , 9F
key如果需要講詳細一點，像是姓名的話，雖然機率很低
10/26 04:09, 9F
→
10/26 04:10, 5年前 , 10F
但還是有可能有人同名，所以它不是個好PK；不過如果它
10/26 04:10, 10F
→
10/26 04:10, 5年前 , 11F
再加上住址，那應該就會夠好。不過這裡面最明顯的當然
10/26 04:10, 11F
→
10/26 04:11, 5年前 , 12F
是學號。
10/26 04:11, 12F
→
10/26 09:07, 5年前 , 13F
我想了一下，Hash Table理論上應該還是可以用才對
10/26 09:07, 13F
→
10/26 09:08, 5年前 , 14F
不能用的應該是Binary Search Tree
10/26 09:08, 14F
推
10/26 11:43, 5年前 , 15F
BST洪1好像有舉例過有一樣的key的解決方法耶只是並不常
10/26 11:43, 15F
→
10/26 11:43, 5年前 , 16F
見
10/26 11:43, 16F
推
10/26 11:46, 5年前 , 17F
4的話像排序data量小用插入排序也不一定比Qsort慢，而且
10/26 11:46, 17F
→
10/26 11:46, 5年前 , 18F
用的空間還比較少，所以data量少的時候看複雜度不準
10/26 11:46, 18F
推
10/26 14:26, 5年前 , 19F
借問一下第2題，False是因為BST的worst case為O(n)的
10/26 14:26, 19F
→
10/26 14:26, 5年前 , 20F
緣故嗎？
10/26 14:26, 20F
→
10/26 14:41, 5年前 , 21F
回樓上，對BST有可能skew
10/26 14:41, 21F
→
10/26 14:41, 5年前 , 22F
BST != binary search
10/26 14:41, 22F
→
10/26 15:09, 5年前 , 23F
謝謝~
10/26 15:09, 23F
→
10/26 17:13, 5年前 , 24F
我也是覺得應該幾乎都有辦法修正...不知道該舉什麼例了
10/26 17:13, 24F
‣ 更多 befdawn 的文章
文章代碼(AID): #1RqJ_feu (Grad-ProbAsk)