ขั้นตอนวิธีของเบรนท์

ขั้นตอนวิธีของเบรนท์ (อังกฤษ: Brent's algorithm) เรียกอีกชื่อหนึ่งว่า "The Teleporting Turtle Algorithm" ได้รับการคิดค้นขึ้นโดย Richard Peirce Brent ในปี 1980 เพื่อใช้ในการตรวจสอบการมีวงรอบ (cycle) ในปัญหาที่มีลักษณะเป็นรายการโยงเดี่ยว ตัวอย่างเช่น ฟังก์ชันวนซ้ำ การแยกตัวประกอบ ตัวสร้างเลขสุ่มเทียม และปัญหาอื่นๆ อีกมากมาย

ขั้นตอนวิธีของเบรนท์ มีหลักการทำงานคล้ายๆ กับขั้นตอนวิธีตรวจสอบการมีวงรอบของฟลอยด์ (Floyd's Tortoise and the Hare algorithm) ข้อได้เปรียบของขั้นตอนวิธีของเบรนท์คือจะใช้เวลาการทำงานน้อยกว่าและสามารถหาความยาวของวงรอบได้โดยตรง ไม่จำเป็นต้องไล่ค้นหาในลำดับย่อยอีกครั้ง

ตัวอย่างการใช้งาน

จากรูป หากเริ่มเดินจากจุด 2 จะมีเส้นทางการเดินดังนี้ 2 → 0 → 6 → 3 → 1 → 6 → 3 → ... พบว่าการวนซ้ำนี้มีวงรอบ เนื่องจากมีการเดินทางซ้ำในเส้นทางเดิม คือ 6 → 3 → 1 ซึ่งขั้นตอนวิธีของเบรนท์มีความสามารถในการตรวจสอบการมีวงจรเช่นนี้ได้นั่นเอง

การอธิบายขั้นตอนวิธี

การทำงานของขั้นตอนวิธีของเบรนท์ เริ่มต้นโดยการกำหนดตัววนซ้ำ 2 ตัวคือ กระต่าย และ เต่า ยืนอยู่ที่จุดเริ่มต้น หลังจากนั้นให้ กระต่าย เดินไปทีละก้าวตามเส้นทาง และจะทำการเคลื่อนย้าย เต่า มาตำแหน่งเดียวกับ กระต่าย เมื่อถึงเวลาที่กำหนด

• โดยหาก กระต่าย เดินไปได้ถึงจุดจบของรายการโยง นั่นแสดงว่า ไม่มีวงรอบ
• แต่หาก กระต่าย เดินไปเจอ เต่า แสดงว่า มีวงรอบ

Flow Chart :

รหัสเทียมแสดงการทำงาน

tortoise = begin_point
hare = begin_point

steps_count = 0
steps_limit = 2

loop forever:
    if hare == end_point: return 'No Cycle Found'
   
    hare = hare.next
    steps_count += 1
   
    if hare == tortoise: return 'Cycle Found'
   
    if steps_count == steps_limit:
        steps_count = 0
        steps_limit *= 2
        // Teleport the tortoise to hare's position
        tortoise = hare

การวิเคราะห์ความซับซ้อนเชิงเวลา

สำหรับขั้นตอนวิธีของเบรนท์นั้น จะมีประสิทธิภาพในการทำงานเท่ากับขั้นตอนวิธีตรวจสอบการมีวงรอบของฟลอยด์ (Floyd's Tortoise and the Hare algorithm) คือ O(λ+μ) โดย μ คือ ความยาวของทางเดินจากจุดเริ่มต้น ไปยังวงรอบ (Cycle) ที่มี λ จุดยอด แต่ในความเป็นจริงแล้ว ขั้นตอนวิธีตรวจสอบการมีวงรอบของเบรนท์ ใช้เวลาในการทำงานเฉลี่ยเร็วกว่าขั้นตอนวิธีตรวจสอบการมีวงรอบของฟลอยด์ประมาณ 36% ซึ่งมีผลทำให้ประสิทธิภาพการทำงานของ "ขั้นตอนวิธีโรห์ของพอลลาร์ด" (Pollard rho algorithm) เพิ่มขึ้นประมาณ 24% อีกด้วย

ขั้นตอนวิธีที่เกี่ยวข้อง

• ขั้นตอนวิธีตรวจสอบการมีวงรอบของฟลอยด์ (Floyd's cycle-finding algorithm)
• ขั้นตอนวิธีโรห์ของพอลลาร์ด (Pollard rho algorithm)