[理工] [軟設]-台大100-資工

看板Grad-ProbAsk作者love5566188 (I'dont kown)時間12年前 (2012/01/26 00:28)推噓4(4推 0噓 16→)

留言20則, 4人參與討論串1/1

http://0rz.tw/AiQ4E 請教一下高手們 2. b. Assume that we have a hash table with collisions resolved by chaining. Attempting to improve the performance of this implementation,we use a red-black tree for each slot instead of an unsorted linked list, resulting in a hash table with collisions resolved "by red-black trees". Assume that a simple uniform hashing function is utilized and the load factor of the hash table is α.What is the running time for unsuccessful searches and insertions for our new implementation,respectively? 要如何用red-black實作hash function,然後求其time complexity? 5. 我想問的是b小題要如何求其running time 和b小題的prefix function是甚麼? 另外兩題我算的，請高手們指教 a. Ω(m+n). d. 1.T:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 a a b a b b a b a b b b a b a b b a a a b b P:a b a b b a a a ﹌ 2. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 a a b a b b a b a b b b a b a b b a a a b b a b a b b a a a ﹌ 3. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 a a b a b b a b a b b b a b a b b a a a b b a b a b b a a a ﹌ 4. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 a a b a b b a b a b b b a b a b b a a a b b a b a b b a a a ﹌ 5. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 a a b a b b a b a b b b a b a b b a a a b b a b a b b a a a ﹌ 6. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 a a b a b b a b a b b b a b a b b a a a b b a b a b b a a a ﹌ 7. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 a a b a b b a b a b b b a b a b b a a a b b a b a b b a a a 8. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 a a b a b b a b a b b b a b a b b a a a b b a b a b b a a a ﹌共8個occurence shifts. 這樣對嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 175.98.50.200

推