Лекция №8. Поиск. Хэширование. Предмет "Структуры и алгоритмы обработки данных"

  • Published on
    07-Jul-2015

  • View
    2.541

  • Download
    5

Embed Size (px)

Transcript

<ul><li> 1. . .. : . , www.grebenshikov.ru </li></ul> <p> 2. - Tprepare = O(n), T f ind = O(n) -Tprepare = O(n log(n)), T f ind = O(log(n)) - O(1) 1 3. {0, 1, . . . , m 1} , S T [0..m 1]. x,xSkey[x]=k T [k] = null, otherwise O(1) 2 4. , - . , : ?, {0, 1, . . . , 109} ? , . 3 5. - - h, - S T . x.key A h(x.key) = k4 6. |A| &gt; 1 . , h(43) = h(89) = h(112) = k : 5 7. : - . h(51) = h(49) = h(63) = i 6 8. : - - . (n), |S| = n. : , - . - , . ? 7 9. - T [0..m 1], n ., = n/m = - . , - = (1 + ) ( - + ).M [T (n)] = (1), = O(1) n = O(m) 8 10. - - - . (-, - ). : 9 11. h(k) = k mod m m: 1. d = 2 . 2. m = 2r r.10 12. : m 2 10.11 13. m = 2r , w- .h(k) = (A k mod 2w ) &gt;&gt; (w r), A mod 2 = 1 2w1 &lt; A &lt; 2w A 2w1 2w 12 14. : m = 8 = 23 , w = 7 1 01 1 0 0 1 A 1 10 1 0 1 1 k10 0 10 10 0 11 0 0 1 1 1001010 0110011 ignore by mod 2w h(k) ignore by &gt;&gt;(wr)13 15. k {1, 2, 3} 14 16. : . , . h : U {0, 1, . . . , m 1} {0, 1, . . . , m 1} h(k, 0), h(k, 1), . . . , h(k, m 1) - 0, 1, . . . , m 1 nm15 17. : A: 1 234 56 7 8 9 10 23 45 78 k = 89: 1. h(89, 0) = 3 2. h(89, 1) = 2 3. h(89, 2) = 9 - !16 18. : - . , . , -. 17 19. - h(k, i) = (h(k, 0) + i) mod m. . - h(k, i) = (h1(k) + i h2(k)) mod m. m = 2r h2(k) - . 18 20. : m! - .. 1 . E[ ] 1 , &lt; 1 n &lt; m19 21. ( ) . n/m . (n 1)/(m 1) . . . (n i)/(m i) . . .ni n , mi &lt; m = i {1, 2, 3, . . . , n 1}n n1n2 1 E[#probes] = 1 + m (1 + m1 (1 + m2 (. . . mn . . .))) 1 + (1 + (1 + (1 + (. . . 1 + . . .)))) 1 + + 2 + 3 + . . .= ii=0 1= 1 20 22. - &lt; 1 const O(1) : 50% 2 90% 10 100% m 21 23. ., ., . . - . : , 2000..116-127. ., ., ., . -: , 2- . - . : - , 2007. .282-315. 22 </p>

Recommended

View more >