การค้นหาแบบกระโดด

จากวิกิพีเดีย สารานุกรมเสรี

การค้นแบบกระโดด (อังกฤษ: jump search) หรือในบางครั้งเรียกว่า การค้นแบบบล็อก (อังกฤษ: block search) เป็นขั้นตอนวิธี สำหรับการค้นหาค่าที่สนใจภายในแถวลำดับที่มีการเรียงลำดับแล้ว โดยจะทำการตรวจสอบข้อมูลในแถวลำดับทุก ๆ j ตัว โดยจะทำการตรวจสอบไปเรื่อย ๆ จนกว่าจะพบข้อมูลที่สนใจ ซึ่งวิธีนี้จะคล้ายกับการค้นแบบเชิงเส้น (Linear Search)

การค้นหาแบบนี้จะได้ผลดีที่สุดเมื่อ j มีค่าเท่ากับ รากที่สองของ n เมื่อ n เป็นความยาวของแถวลำดับ

รหัสเทียม[แก้]

ข้อมูลขาเข้า : แถวลำดับที่เรียงลำดับข้อมูลแล้ว มีความยาวเท่ากับ n และให้ s คือค่าที่เราสนใจ
ข้อมูลขาออก : จะส่งตำแหน่งของข้อมูลที่สนใจออกมา และถ้าหากไม่พบข้อมูลที่สนใจ จะไม่ส่งค่าอะไรกลับมา
ให้ a มีค่าเท่ากับ 0
ให้ b มีค่าเท่ากับ n
ทำงานไปเรื่อย ๆ เมื่อ ( (ค่าที่น้อยกว่าระหว่าง b กับ n ) -1 < s) เป็นจริง{
a = b
b = b + √n
ถ้า a มากกว่าหรือเท่ากับ n ให้ออกจากวงวน และไม่คืนค่าอะไรออกมา
}
ทำงานไปเรื่อย ๆ เมื่อ ( ถ้า a น้อยกว่า s) เป็นจริง{
a = a+1
ถ้า a เท่ากับ ค่าที่น้อยกว่าระหว่าง b กับ n ให้ออกจากวงวนและไม่คืนค่าอะไรออกมา
}
ถ้า a = s ก็ให้ทำการคืนตำแหน่ง a ออกไป
ถ้าไม่เช่นนั้นให้ ไม่ต้องคืนค่าอะไรออกมา


ประสิทธิภาพการทำงาน[แก้]

การค้นหาแบบกระโดด (Jump Search) หากใช้ค่าที่ดีที่สุดในการกระโดดค้นหา คือ √n เมื่อ n เป็นความยาวของแถวลำดับ แล้ว จะมีประสิทธิภาพเท่ากับ O(√n) ซึ่งดีกว่าการค้นแบบเชิงเส้น (Linear Search) ที่มีประสิทธิภาพเท่ากับ O\left(n\right) แต่ก็มีประสิทธิภาพน้อยกว่า การค้นแบบทวิภาค (Binary Search) ที่มีประสิทธิภาพเท่ากับ O\left(\log n\right)

เราสามารถเพิ่มประสิทธิภาพการทำงานได้โดยการทำการค้นแบบกระโดดหลายระดับในแถวลำดับย่อย โดยสำหรับ k ระดับของการค้นแบบกระโดด ที่มีบล็อกขนาด m ที่ l ระดับ จะมีประสิทธิภาพการทำงานเท่ากับ O (n^(k-l))

อ้างอิง[แก้]

ดูเพิ่ม[แก้]