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

[love5566188 (I'dont kown)]

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
推 pikachu123:5.我不曉得你在寫甚麼 這題考KMP阿
→ pikachu123:prefix function 就是Failure function
→ pikachu123:計算failure function 花O(m)阿
→ pikachu123:                        Ω
→ pikachu123:跑matching主程式花Ω(n)總共Ω(m+n)
→ pikachu123:d.我目視法得shift=12 XDD
→ pikachu123:P[1...n]=T[S+1...S+n]
→ pikachu123:shift就是叫你跑matching主程式拉
→ pikachu123:不過這題用看的就可以了XDDD 台大還蠻好心的
推 pikachu123:2.那個是叫你求Un拉 原本Un=α 你用紅黑樹
→ pikachu123:search次數就變少了 紅黑樹樹高O(logn)
→ pikachu123:所以新的Un=logα
推 metalalive:SORRY請教一下load factor α的意思是什麼嗎? 我有查
→ metalalive:它寫的意義我看的沒有很了解
→ love5566188:請問failure function起始值是0還是-1? 96清大有一題
→ love5566188:板上有人寫-1開始，然後有人寫0，我都搞混了
推 pikachu123:看他index從哪裡開始 台大這題從1開始 所以沒對到填0
→ pikachu123:loading factor α=n/b*s 也就是每個Bucket的平均data
→ pikachu123:數 他hashing是Uniform的
→ sneak: search次數就變少 https://daxiv.com