[問題] 比較理論性的東西

看板C_and_CPP (C/C++)作者 (離不開的別離)時間16年前 (2010/01/12 14:20), 編輯推噓5(5016)
留言21則, 12人參與, 最新討論串1/1
這是資料結構的問題 Compare worst-case search times for a 4096-element block of data. How many comparisons are requare for sequential,binary,and ideal hash functions? 我不知道答案 蠻急的希望大家幫忙一下 跟專業網友討論出來的答案是 1.4096 2.12 3.1 不知道答案是不是正確的 希望大家能協助一下 謝謝 -- ╭───╮ ∕◢██◣李組長眉頭一皺, \ ㄟˇㄏ / ㄧ..ㄧ + 覺得案情並不單純。 /︷\ $snegi ▅▅▆ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.41.196.233 ※ 編輯: shyanglong 來自: 114.41.196.233 (01/12 14:26) ※ 編輯: shyanglong 來自: 114.41.196.233 (01/12 14:31)

01/12 16:03, , 1F
data有沒有sorted ?
01/12 16:03, 1F

01/12 16:04, , 2F
問題問多少次 comparison, 你答案可以求到小數?
01/12 16:04, 2F

01/12 16:12, , 3F
樓上好像看錯了?
01/12 16:12, 3F

01/12 16:12, , 4F
我沒看到小數在哪裡 -.-??
01/12 16:12, 4F

01/12 16:22, , 5F
It's nothing theoretical, just TRIVIAL (丟筆)
01/12 16:22, 5F

01/12 16:42, , 6F
a 大累了~ 聽首歌吧~ XD
01/12 16:42, 6F

01/12 16:42, , 7F
的確要看有沒有 sorted, 不然根本不能用 binary search
01/12 16:42, 7F

01/12 16:44, , 8F
咦? 問題不是問 "How many comparisons" 嗎?
01/12 16:44, 8F

01/12 16:46, , 9F
題目就只問 Worst case 嘛,管它有無排序
01/12 16:46, 9F

01/12 16:56, , 10F
沒排序根本不可能用binary search 吧
01/12 16:56, 10F

01/12 17:00, , 11F
呀!!!!! 我明白大家說 沒小數 的意思了 orz 耍笨了
01/12 17:00, 11F

01/12 17:01, , 12F
btw, binary search 不是應該是 13 次嗎? 應該要顧及
01/12 17:01, 12F

01/12 17:02, , 13F
搜尋值不在 set 裡的情況吧
01/12 17:02, 13F

01/12 17:22, , 14F
XD 我也發現小數在哪裡了.... XD
01/12 17:22, 14F

01/12 19:23, , 15F
乍看真的看到小數,嚇一跳,以前怎麼沒學過
01/12 19:23, 15F

01/12 23:39, , 16F
data block 為什麼還要sort 不是sort好了嗎? 所以log(n)壓
01/12 23:39, 16F

01/13 01:38, , 17F
可以請教 洪逸 大師,是他帶我入門的 = =
01/13 01:38, 17F

01/13 03:23, , 18F
http://tinyurl.com/3abygs 就是要先排序
01/13 03:23, 18F

01/13 04:54, , 19F
Binary Search 要排序,不代表 sequential、hash 要排序
01/13 04:54, 19F

01/16 02:05, , 20F
hash function運算若考慮有collision 應該就不是O(1)
01/16 02:05, 20F

01/16 02:15, , 21F
不過既然是perfect/ideal hash 就當他是O(1)
01/16 02:15, 21F
文章代碼(AID): #1BJ1Iidt (C_and_CPP)
文章代碼(AID): #1BJ1Iidt (C_and_CPP)