Page 46 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 46
15-36 โครงสร้างข้อมูลและขั้นตอนว ิธี
k
1 23 … k - 2 k - 1 k
ค่าที่ตำ�แหน่งสุดท้ายมากกว่าค่าที่สืบค้น
ตรวจสอบข้อมูลถอยหลังในช่วงกระโดด 1 ถึง k-1
ภาพที่ 15.9 การเปรียบเทยี บภายในชว่ ง k
ท�ำให้ก ารเปรียบเทียบส�ำหรับการกร ะโดดท้ังหมดเท่ากับ nkk-1คคร้ังรั้ง
และการเปรียบเทียบห ลังการกร ะโดดค ร้ังส ุดท้ายเท่ากับ
กค า่ารkเปทรียี่เหบมเทาะียสบมทคั้งือหมคด่าคkือที่ทnk�ำใ+ห้(knk-1)+ค(รkั้ง-1)
ดังน้ัน น้อยท ่ีสุด
ดังน้ัน
ก�ำหนดให้ f(k) = n + (k-1)
k
ส่ิงท่ีต ้องการค ือ ค่า k ที่ท�ำให้ f(k) น้อยท ่ีสุด หรือ mink f(k)
ซ่ึงหาค ่าน้อยส ุดโดยก ารใช้อ นุพันธ์
f(k) = 0
d n
dk ( k + k-1) = 0
n = 0
k2 + 1 n
nk 2
1 =
k2 =
ซ่ึงจะได้ k = n
ดังนั้นค่า k ที่เหมาะส มคือ n
1. โครงสรา้ งข อ้ มูลของการค้นหาข้อมูลแบบกระโดด
ส�ำหรับโครงสร้างข ้อมูลท ี่ใช้ในก ารค้นหาแ บบกระโดดนั้นจะเป็นแบบอ าร์เรย์โดยข้อมูลต ้องม ีการจ ัดเรียงมา
ก่อน
