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

ขั้นตอนวิธีของเบรนท์Brent's cycle detection algorithm: Algorithmic cryptanalysis, Antoine Joux, Chapman & Hall/CRC Taylor & Francis Group, 2009, P.266 () เรียกอีกชื่อหนึ่งว่า "The Teleporting Turtle Algorithm" ได้รับการคิดค้นขึ้นโดย Richard Peirce Brent ในปี 1980 เพื่อใช้ในการตรวจสอบการมีวงรอบhttp://lab.iisec.ac.jp/labs/tanaka/publications/pdf/conference/conference-86-02.pdf (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