ความซับซ้อนของการขุด/ลงนามแฮช

สำหรับอินพุตแบบสุ่ม แต่ละบิตมีความน่าจะเป็น $\frac{1}{2}$ ให้เป็นศูนย์ เนื่องจากเราคิดว่าความเป็นอิสระ (ฟังก์ชันแฮชในอุดมคติแสดงถึงสมมติฐานนี้) สำหรับแต่ละอินพุตความน่าจะเป็น $4$ ศูนย์ในบิตนำหน้าคือ $\frac{1}{2^4}=\frac{1}{16}$.

หลังจากนั้น $k$ การคำนวณ เนื่องจากเราพิจารณาว่าแต่ละเอาต์พุตเป็นอิสระต่อกัน (เนื่องจากเป็นฟังก์ชันแฮชในอุดมคติ) ความน่าจะเป็นที่จะรออย่างแน่นอน $i$ ขั้นตอนที่เป็นผลลัพธ์ที่ดีคือ $\frac{1}{16}\left(15/16\right)^{i-1}$. (เนื่องจากคุณมีผลลัพธ์ที่ไม่ถูกต้องสำหรับ $(i-1)$ แฮชแล้วก็คนโง่)

และความคาดหวังของเวลาในการคำนวณคือ $\sum^{\infty}_{i=1} i\frac{1}{16}\left(15/16\right)^{i-1}= \frac{1}{16}\sum^{\infty}_{j=1} \sum^{\infty}_{i=j}\left(15/16\right)^{i-1}= \frac{1}{16}\sum^{\infty}_{j=1} \sum^{\infty}_{i=0}\left(15/16\right)^{j+i-1 }$

$$=\frac{1}{16}\sum^{\infty}_{j=1} \left(15/16\right)^{j-1}\sum^{\infty}_{i= 0}\left(15/16\right)^{i} $$ $$= \frac{1}{16}\sum^{\infty}_{j=1} \left(15/16\right)^{j-1}\frac{1}{1/16}$ $ $$=\sum^{\infty}_{j=0} \left(15/16\right)^{j} =16$$.

จากนั้นคุณต้องคำนวณโดยเฉลี่ย $16$ แฮชเพื่อค้นหาสิ่งที่ดี

คุณสามารถสรุปการพิสูจน์นี้ได้โดยง่ายโดยการแทนที่ $16$ โดย $2^m$และคุณจะอนุมานได้ว่าคุณต้องคำนวณโดยเฉลี่ย $2^m$ กัญชา

โปรดสังเกตว่าเนื่องจากเราเลือกพิกัดที่เราต้องการให้มีศูนย์ล่วงหน้า ผลลัพธ์ทั้งหมดของฟังก์ชันแฮชจึงไม่สำคัญถ้าเราดูจำนวนแฮชที่เราควรคำนวณ (แต่สามารถทำได้ถ้าเราดูเวลาของการคำนวณ ของ $H$).