|
|
(ไม่แสดง 10 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน) |
แถว 1: |
แถว 1: |
| {{หัวคำบรรยาย|204512}} | | {{หัวคำบรรยาย|204512}} |
| + | '''จดบันทึกคำบรรยายโดย:''' |
| + | :นายมนต์ชัย สารทอง |
| + | :นายอุกฤษณ์ กุลดิลก 50653971 |
| + | |
| + | บทนี้จะกล่าวถึงทฤษฎีความน่าจะเป็นพื้นฐาน จากนั้นจะพิจารณาโครงสร้างข้อมูลแบบสุ่มสองแบบ คือ skip list และ universal hash |
| + | |
| ==Balls & Bins== | | ==Balls & Bins== |
| :มีถัง n ถัง | | :มีถัง n ถัง |
แถว 121: |
แถว 127: |
| == ตัวแปรสุ่มที่สำคัญ == | | == ตัวแปรสุ่มที่สำคัญ == |
| | | |
− | === 1. Indicator R.V. === | + | === 1. ตัวแปรสุ่มแบบ indicator === |
− | :มีค่า 0, 1
| + | มีตัวแปรสุ่มที่มีค่า 0 หรือ 1 สังเกตว่า |
− | ถ้า X เป็น Indicator R.V.
| |
− | :<math>E[X] = Pr[X=1]</math>
| |
| | | |
− | === 2. Binomial R.V. === | + | {{thm-box| |
| + | '''Proposition:''' ถ้า X เป็น Indicator R.V. |
| + | <center><math>E[X] = \Pr[X=1]</math></center>}} |
| + | {{begin-pf}} |
| + | '''Proof:''' จากนิยาม เราได้ว่า <math>E[X] = 0\cdot\Pr[X=0] + 1\cdot\Pr[X=1] = \Pr[X=1]</math> |
| + | {{end-pf}} |
| + | |
| + | === 2. ตัวแปรสุ่มแบบ binomial === |
| :มีการทดลองสำเร็จด้วยความน่าจะเป็น p | | :มีการทดลองสำเร็จด้วยความน่าจะเป็น p |
| :ทดลอง n ครั้ง แบบไม่ขึ้นต่อกัน | | :ทดลอง n ครั้ง แบบไม่ขึ้นต่อกัน |
แถว 173: |
แถว 184: |
| เมื่อกล่าวว่าเหตุการณ์ใดเกิดขึ้นด้วยความน่าจะเป็นสูง จะหมายความว่า เหตุการณ์ดังกล่าวขะไม่เกิดขึ้นด้วยความน่าจะเป็นไม่เกิน <math>\frac{1}{n^c}</math> เมื่อ c>0 และ n คือ parameter ของระบบ | | เมื่อกล่าวว่าเหตุการณ์ใดเกิดขึ้นด้วยความน่าจะเป็นสูง จะหมายความว่า เหตุการณ์ดังกล่าวขะไม่เกิดขึ้นด้วยความน่าจะเป็นไม่เกิน <math>\frac{1}{n^c}</math> เมื่อ c>0 และ n คือ parameter ของระบบ |
| | | |
− | '''<u>Lemma</u>''': skip list ที่มีข้อมูล n ตัวจะมีความสูง O(log n) ด้วยความน่าจะเป็นสูง | + | {{thm-box|'''Lemma:''' skip list ที่มีข้อมูล ''n'' ตัวจะมีความสูง ''O''(log ''n'') ด้วยความน่าจะเป็นสูง}} |
− | | + | {{begin-pf}} |
− | '''<u>Proof</u>''' พิจารณาข้อมูล x ใดๆ ความน่าจะเป็นที่ระดับของ x>k | + | '''Proof:''' พิจารณาข้อมูล x ใดๆ ความน่าจะเป็นที่ระดับของ x>k |
| :'''Pr[ระดับ x>k] =''' <math>\frac{1}{2^k}</math> | | :'''Pr[ระดับ x>k] =''' <math>\frac{1}{2^k}</math> |
| ให้เหตุการณ์ <math>A_i</math> แทนเหตุการณ์ที่ข้อมูลตัวที่ i มีระดับมากกว่า k | | ให้เหตุการณ์ <math>A_i</math> แทนเหตุการณ์ที่ข้อมูลตัวที่ i มีระดับมากกว่า k |
แถว 186: |
แถว 197: |
| :'''Pr[ความสูงไม่เกิน k] = 1 - Pr[มีข้อมูลบางตัวมีระดับมากกว่า k]''' <math>\le 1 - \frac{n}{2^k} = 1 - \frac{n}{2^{clogn}} = 1 - \frac{1}{n^{c-1}}</math> | | :'''Pr[ความสูงไม่เกิน k] = 1 - Pr[มีข้อมูลบางตัวมีระดับมากกว่า k]''' <math>\le 1 - \frac{n}{2^k} = 1 - \frac{n}{2^{clogn}} = 1 - \frac{1}{n^{c-1}}</math> |
| ถ้า c>2 , เหตุการณ์ดังกล่าวจะเกิดด้วยความน่าจะเป็นสูง | | ถ้า c>2 , เหตุการณ์ดังกล่าวจะเกิดด้วยความน่าจะเป็นสูง |
| + | {{end-pf}} |
| + | |
| :'''Pr[เดิน k node] =''' <math>k\cdot\frac{1}{2^k}</math> | | :'''Pr[เดิน k node] =''' <math>k\cdot\frac{1}{2^k}</math> |
− | '''<u>Thm</u>''' Expected search time ของ skip list ที่มีข้อมูล n ตัว คือ O(log n)
| |
| | | |
| + | {{thm-box|'''Theorem:''' Expected search time ของ skip list ที่มีข้อมูล ''n'' ตัว คือ ''O''(log ''n'')}} |
| + | {{begin-pf}} |
| '''<u>Proof</u>''' | | '''<u>Proof</u>''' |
| :ให้ H = ความสูง = O(log n) | | :ให้ H = ความสูง = O(log n) |
| :ให้ <math>T_i</math> เป็นเวลาที่ใช้ในชั้นที่ i | | :ให้ <math>T_i</math> เป็นเวลาที่ใช้ในชั้นที่ i |
| :<math>T = \sum_{i=1}^H T_i</math> | | :<math>T = \sum_{i=1}^H T_i</math> |
− | :<math>E[T] = E[\sum_{i=1}^H T_i] = \sum_{i=1}^H E[T_i] = O(log n)</math> | + | :<math>E[T] = E[\sum_{i=1}^H T_i] = \sum_{i=1}^H E[T_i] = O(\log n)</math> |
| + | {{end-pf}} |
| | | |
| == Hashing == | | == Hashing == |
บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง
จดบันทึกคำบรรยายโดย:
- นายมนต์ชัย สารทอง
- นายอุกฤษณ์ กุลดิลก 50653971
บทนี้จะกล่าวถึงทฤษฎีความน่าจะเป็นพื้นฐาน จากนั้นจะพิจารณาโครงสร้างข้อมูลแบบสุ่มสองแบบ คือ skip list และ universal hash
Balls & Bins
- มีถัง n ถัง
- มีบอล n ลูก
![{\displaystyle {\rm {Pr[first\ bin\ is\ empty]=}}\left({{\rm {1-}}{\frac {\rm {1}}{\rm {n}}}}\right)^{\rm {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/872ae7759506a112be7071c0d265611466e058b1)
Random Variable
- นิยาม
- สำหรับตัวแปรสุ่ม X
![{\displaystyle \sum \limits _{i=-\infty }^{\infty }{i\cdot \Pr[X=i]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e3c91784fe9c9663e402366d27ca41b9012a195)
Ex.1 มีลูกเต๋า 2 ลูก โยนทีละลูก
ให้ตัวแปรสุ่ม
แต้มบนลูกเต๋าลูกที่ 1
แต้มบนลูกเต๋าลูกที่ 2
แต้มรวม
![{\displaystyle E[Y_{1}]=(1+2+3+...+6)\cdot {\frac {1}{6}}=3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f77b660319b5ac06155587ebf8aea3cc6b6c4db)
![{\displaystyle E[Y_{2}]=(1+2+3+...+6)\cdot {\frac {1}{6}}=3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/844ed0f7193d0ef657f6bcccf2eef0f6e44ce5df)
![{\displaystyle E[Y]=2\cdot {\frac {1}{6}}\cdot {\frac {1}{6}}+3\cdot 2\cdot {\frac {1}{36}}+4\cdot 3\cdot {\frac {1}{36}}+5\cdot .....=7}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5609739b81381559b0049f44f8e8deb79cce8b01)
Linearity of Expectation
สำหรับตัวแปรสุ่ม X, Y
จาก Ex.1 ให้ตัวแปรสุ่ม X แทนจำนวนถังว่าง
![{\displaystyle E[X]=?}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fed450511cffa0a2dc75677b3834b8e8eac00989)
ให้ตัวแปรสุ่ม
ถ้าถังที่ i ว่าง
กรณีอื่นๆ
สังเกตว่า
![{\displaystyle X=\sum \limits _{i=1}^{n}{X_{i}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc5dfe124680aa1a64aa84dad88b4ec57bfbbd4f)
ดังนั้น
![{\displaystyle E[X]=E[\sum \limits _{i=1}^{n}{X_{i}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/801de500a1e2efcb14962d97f5b66467a5cfad32)
โดย Linearity of Expectation
![{\displaystyle E[X_{i}]=0\cdot Pr[X_{i}=0]+1\cdot Pr[X_{i}=1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3760a6ac32ce42b59374146bacff546dcb2c4692)
![{\displaystyle E[X_{i}]=Pr[X_{i}=1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4a09691e19daaccd3bfd412a6d0f965794b7f68)
![{\displaystyle E[X_{i}]=(1-{\frac {1}{n}})^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d51e4c1cb6e93ec8a9b0e4f0e9029a7cb2d54e3)
![{\displaystyle E[X]=\sum \limits _{i=1}^{n}{E[X_{i}]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf4ad4e1484061a7df295923212bd111778bf5cb)
![{\displaystyle E[X]=\sum \limits _{i=1}^{n}{(1-{\frac {1}{n}})^{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0557ac0e512b3f4a4c7596fee061461dc318d88)
![{\displaystyle E[X]=n(1-{\frac {1}{n}})^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/201a81a125622b9c3f670015530f328eec2f407e)
![{\displaystyle E[X]\approx {\frac {n}{e}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62ae210f164cc3574d76e37624609fd08df4cf7e)
![{\displaystyle 1+X\leq e^{X}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2142bd6530ac09968f0e2bbf18b77dcc0ff3597a)
![{\displaystyle (1-{\frac {1}{n}})^{n}\leq (e^{-{\frac {1}{n}}})=e^{-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85ebb3e27762ef8634fa872c4312df9237259450)
![{\displaystyle (1-{\frac {t}{n}})^{n}\leq (e^{-{\frac {t}{n}}})=e^{-t}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84f65e0398cbb72f47de53d0e78602a40672a575)
มีบอล m ลูก
มีถัง n ถัง
ให้
จำนวนถังว่าง
หา E[X]
![{\displaystyle E[X]=E[\sum \limits _{i=1}^{n}{X_{i}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/801de500a1e2efcb14962d97f5b66467a5cfad32)
![{\displaystyle E[X]=\sum \limits _{i=1}^{n}{E[X_{i}]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf4ad4e1484061a7df295923212bd111778bf5cb)
![{\displaystyle E[X]=\sum \limits _{i=1}^{n}{(1-{\frac {1}{n}})^{m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ac8d92a4cf6d0c157d83c76f3a2d9d01644bc10)
![{\displaystyle E[X]=n(1-{\frac {1}{n}})^{m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b99da437eb4248c993a8b471f5520595d2c30c2c)
ต้องโยนบอลกี่ลูก X จะเข้าใกล้ 0
![{\displaystyle E[X]=n(1-{\frac {1}{n}})^{m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b99da437eb4248c993a8b471f5520595d2c30c2c)
![{\displaystyle E[X]=[n(1-{\frac {1}{n}})^{n}]^{\frac {m}{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b102b3aaf43f9c3e911fead1dcf4f3f9c4a444d)
![{\displaystyle E[X]\leq n(e^{-1})^{\frac {m}{n}}={\frac {n}{e^{\frac {m}{n}}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37bd3e4e1b2a73d962acfe9cd9ea9b3b2bb47869)
![{\displaystyle {\frac {n}{e^{\frac {m}{n}}}}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ecc3b77520a6bc63dd9cdc69b1733642dcb3435)
![{\displaystyle n=e^{\frac {m}{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca386caba19d6b7bf91874447cf9a251e43aaddb)
![{\displaystyle ln\ n={\frac {m}{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f559a0d9cdee23ce2cc342101e74fc6852e9a913)
![{\displaystyle m=n\ ln\ n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59508a87e5be48a9178d863d5304794296005ea2)
ให้
![{\displaystyle E[X]=n(1-{\frac {1}{n}})^{cn\ ln\ n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/951924294a8c657f690973fdb0080bc312bf5ab0)
![{\displaystyle E[X]\leq {\frac {n}{n^{c}}}={\frac {1}{n^{c-1}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45b29328a344d374d1acc88be44d67e1b4479e13)
- Thm
- สำหรับตัวแปรสุ่ม X, Y
![{\displaystyle E[X+Y]=E[X]+E[Y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea2251900ec2b03db1d6f870336155a2a09ff7f1)
- Proof
![{\displaystyle E[X+Y]=\sum \limits _{i=-\infty }^{\infty }{i\cdot Pr[X+Y=i]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32b83d952561845d379227ca45709ad3fd3f9a8a)
![{\displaystyle E[X+Y]=\sum \limits _{i=-\infty }^{\infty }{i\cdot [\sum \limits _{j=-\infty }^{\infty }{Pr[X=j,Y=i-j]}]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7ea0acc1a12bf4bda04b7a363aa239e5b302cba)
- ให้
![{\displaystyle i=a+b,j=b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ea719f35a793751e2e34605004f05c63c5ddb0e)
![{\displaystyle E[X+Y]=\sum \limits _{a=-\infty }^{\infty }{\sum \limits _{b=-\infty }^{\infty }{(a+b)Pr[X=b,Y=a]}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f79501fe89bdabfe921e4e4d9e8e404ee594bc3)
![{\displaystyle E[X+Y]=\sum \limits _{a=-\infty }^{\infty }{\sum \limits _{b=-\infty }^{\infty }{a\cdot Pr[X=b,Y=a]}}+\sum \limits _{a=-\infty }^{\infty }{\sum \limits _{b=-\infty }^{\infty }{b\cdot Pr[X=b,Y=a]}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99f8af1aae27ea9cfe37a81eedf3a459f7bdf7a0)
![{\displaystyle E[X+Y]=\sum \limits _{a=-\infty }^{\infty }{a[\sum \limits _{b=-\infty }^{\infty }{Pr[X=b,Y=a]}]}+\sum \limits _{b=-\infty }^{\infty }{b[\sum \limits _{a=-\infty }^{\infty }{Pr[X=b,Y=a]}]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cdf8f500331398d760391cf25291846ae13b5c0)
![{\displaystyle E[X+Y]=Pr[Y=a]+Pr[X=b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c7fa0aea59c4e1bf4820c42307ebbef7c05729a)
ตามต้องการ
ตัวแปรสุ่มที่สำคัญ
1. ตัวแปรสุ่มแบบ indicator
มีตัวแปรสุ่มที่มีค่า 0 หรือ 1 สังเกตว่า
Proposition: ถ้า X เป็น Indicator R.V.
Proof: จากนิยาม เราได้ว่า
2. ตัวแปรสุ่มแบบ binomial
- มีการทดลองสำเร็จด้วยความน่าจะเป็น p
- ทดลอง n ครั้ง แบบไม่ขึ้นต่อกัน
- จำนวนครั้งของการทดลองที่สำเร็จ จะเป็นตัวแปรสุ่มแบบ
- binomial => มี พารามิเตอร์ (n, p)
สำหรับตัวแปรสุ่ม X แบบ binomial ที่มี parameter (n, p)
ให้
ถ้าการทดลองครั้งที่ i สำเร็จ
กรณีอื่นๆ
![{\displaystyle X=\sum \limits _{i=1}^{n}{X_{i}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc5dfe124680aa1a64aa84dad88b4ec57bfbbd4f)
ดังนั้น
![{\displaystyle E[X]=E[X_{1}+X_{2}+...+X_{n}]=\sum \limits _{i=1}^{n}{E[X_{i}]}=np}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5bd714c25702f8fb405cc127e2fcdb565e88e5e6)
![{\displaystyle Pr[X=a]=C(n,a)\cdot p^{a}(1-p)^{n-a}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f2d422c3102289f0149a89780f9bad8b5bdb55d)
เมื่อ
แทนสัมประสิทธิ์ทวินาม ที่มีค่าเท่ากับ
ทั้งนี้เนื่องจาก ในการทดลอง n ครั้ง จะทดลองสำเร็จ a ครั้ง มีจำนวนรูปแบบที่เป็นไปได้ทั้งหมดเท่ากับ
แบบ และแต่ละแบบ มีความน่าจะเป็นที่จะเกิดขึ้นเท่ากับ
3. Geometric R.V.
- มีเหรียญที่ออกหัวด้วยความน่าจะเป็น p
- จำนวนครั้งที่โยนจนได้หัว เป็นตัวแปรสุ่มแบบ geometric [พารามิเตอร์ p]
- ให้ r.v. X เป็นตัวแปรสุ่มแบบ geometric ที่มี parameter p
![{\displaystyle Pr[X=i]=p(1-p)^{i-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/421486504d4498fb008c9b838202cac98ac73faa)
![{\displaystyle E[X]={\frac {1}{p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db85df0d1c494b9c8488276e542ac7a055a92492)
Skip List
#---------------->O---------->#
|
#---->O---------->O------->O->#
| | |
#---->O------->O->O---->O->O->#
| | | | |
#->O->O->O->O->O->O->O->O->O->#
ในการตัดสินใจว่าแต่ละโหนดจะมีความสูงขึ้นไปเท่าไหร่ จะใช้ความน่าจะเป็น เช่น การโยนเหรียญ เมื่อมีการเพิ่มข้อมูลใหม่ จะค้นหาจนกระทั่งพบช่องที่สามารถลงได้ จากนั้นก็ใช้ความน่าเป็น ในการดูว่าจะให้โหนดที่เพิ่มลงไปใหม่ควรจะมีความสูงเท่าไหร่
เมื่อกล่าวว่าเหตุการณ์ใดเกิดขึ้นด้วยความน่าจะเป็นสูง จะหมายความว่า เหตุการณ์ดังกล่าวขะไม่เกิดขึ้นด้วยความน่าจะเป็นไม่เกิน
เมื่อ c>0 และ n คือ parameter ของระบบ
Lemma: skip list ที่มีข้อมูล n ตัวจะมีความสูง O(log n) ด้วยความน่าจะเป็นสูง
Proof: พิจารณาข้อมูล x ใดๆ ความน่าจะเป็นที่ระดับของ x>k
- Pr[ระดับ x>k] =
![{\displaystyle {\frac {1}{2^{k}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7247a56934790ab90e0d85e41de5c34f629182da)
ให้เหตุการณ์
แทนเหตุการณ์ที่ข้อมูลตัวที่ i มีระดับมากกว่า k
- Pr[
] = ![{\displaystyle {\frac {1}{2^{k}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7247a56934790ab90e0d85e41de5c34f629182da)
ให้เหตุการณ์ A แทนเหตุการณ์ที่มีข้อมูลบางตัวมีระดับมากกว่า k
![{\displaystyle A=\bigcup _{i=1}^{n}A_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcbf6982abcd9d95239304feb731a517babad2e0)
ดังนั้น
![{\displaystyle Pr[A]\leq \sum _{i=1}^{k}Pr[A_{i}]={\frac {n}{2^{k}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/038b18cf22571336a7d42d5984fe95227de17732)
ให้ K = c log n = O(log n) จะได้ว่า
- Pr[ความสูงไม่เกิน k] = 1 - Pr[มีข้อมูลบางตัวมีระดับมากกว่า k]
![{\displaystyle \leq 1-{\frac {n}{2^{k}}}=1-{\frac {n}{2^{clogn}}}=1-{\frac {1}{n^{c-1}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ed6b8126f26ef01fd04865a2d94594e4e49e40e)
ถ้า c>2 , เหตุการณ์ดังกล่าวจะเกิดด้วยความน่าจะเป็นสูง
- Pr[เดิน k node] =
![{\displaystyle k\cdot {\frac {1}{2^{k}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ab1c3c7b8666a9487669ab1bbb4623b7e92b911)
Theorem: Expected search time ของ skip list ที่มีข้อมูล n ตัว คือ O(log n)
Proof
- ให้ H = ความสูง = O(log n)
- ให้
เป็นเวลาที่ใช้ในชั้นที่ i
![{\displaystyle T=\sum _{i=1}^{H}T_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ae55d4751cc832cb03afd9a6bece82048ee4315)
![{\displaystyle E[T]=E[\sum _{i=1}^{H}T_{i}]=\sum _{i=1}^{H}E[T_{i}]=O(\log n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f56a00ca5335b924729d5c9b63cf8d0680d449a)
Hashing
ในส่วนนี้ จะให้
แทนเซตของคีย์
และ
แืทนเซตของดัชนีในตาราง
hash function
จะส่งคีย์ไปยังตำแหน่งในตาราง
เลือกจำนวนเฉพาะ p > M
ให้
สำหรับ
และ
![{\displaystyle h_{ab}(x)=((ax+b){\bmod {p}}){\bmod {N}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ff27872a391736394c9bbb99ff89da4fb9a748c)
![{\displaystyle |H|=(p-1)p}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa53b5a8bbfed28d3dda0925c92af261b463e54f)
- Lemma
- สำหรับ x, y ที่
![{\displaystyle x\neq y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f51b711ca7f932963cdb268b0817dc72d6258733)
- จำนวน
ที่
![{\displaystyle h_{ab}(x)=h_{ab}(y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4684b47e43b840a1c47ac20f48bca87e3b9cf2de)
- ไม่เกิน
ตัว
- Proof
- ให้
![{\displaystyle ax+b\equiv r{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ef6ef9a53b691ad8199a0a0612963d15b68b1c0)
![{\displaystyle ay+b\equiv s{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3d787c4dd79f7bb44573310d9ba71ad76a071c0)
- (1) ถ้า
- พิสูจน์ด้วยข้อขัดแย้ง
- assume
![{\displaystyle ax\equiv ay{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22308412ed24f7a4710240324895f370866949dc)
- x = y
- (2) ถ้า
แล้ว
- จำนวนคู่ r, s ที่สอดคล้อง
![{\displaystyle \leq p[{\frac {p}{N}}-1]\leq {\frac {p(p-1)}{N}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05289c21ed1de8a5d24ae7faf3fb91ca84025a64)
- (3) พิจารณา คู่ r, s คู่หนึ่ง ที่
- จะหาค่า a, b ที่
![{\displaystyle ax+b\equiv r{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ef6ef9a53b691ad8199a0a0612963d15b68b1c0)
![{\displaystyle ay+b\equiv s{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3d787c4dd79f7bb44573310d9ba71ad76a071c0)
![{\displaystyle ax-ay\equiv r-s{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d56bbaaeaae95352f38e7273a79a874be339f017)
![{\displaystyle a(x-y)\equiv r-s{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/73e15fd3d1310cb40fa76613032f693dd550074d)
![{\displaystyle a\equiv (r-s)\cdot (x-y)^{-1}{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27fd488e9b9b9d5794378350bf34ab56277fc3fa)
- แต่ละคู่ r, s จะมี a, b คู่เดียว
จาก (1), (2), (3), มี a, b ไม่เกิน
คู่