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

ขั้นตอนวิธีของเบรนท์ () เรียกอีกชื่อหนึ่งว่า "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)

อ้างอิง 

ขั้นตอนวิธี
หมวดหมู่:ขั้นตอนวิธีการจัด

en:Cycle detection#Brent's algorithm