Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ขั้นตอนวิธีของเบรนท์ (อังกฤษ: 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)
อ้างอิง
- Brent's cycle detection algorithm: Algorithmic cryptanalysis, Antoine Joux, Chapman & Hall/CRC Taylor & Francis Group, 2009, P.266
- http://lab.iisec.ac.jp/labs/tanaka/publications/pdf/conference/conference-86-02.pdf[]
- (1980), (PDF), BIT, 20 (2): 176–184, doi:10.1007/BF01933190, คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2009-09-24, สืบค้นเมื่อ 2011-09-15.
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
khntxnwithikhxngebrnth xngkvs Brent s algorithm eriykxikchuxhnungwa The Teleporting Turtle Algorithm idrbkarkhidkhnkhunody Richard Peirce Brent inpi 1980 ephuxichinkartrwcsxbkarmi cycle inpyhathimilksnaepnraykaroyngediyw twxyangechn karaeyktwprakxb twsrangelkhsumethiym aelapyhaxun xikmakmay khntxnwithikhxngebrnth mihlkkarthangankhlay kbkhntxnwithitrwcsxbkarmiwngrxbkhxngflxyd Floyd s Tortoise and the Hare algorithm khxidepriybkhxngkhntxnwithikhxngebrnthkhuxcaichewlakarthangannxykwaaelasamarthhakhwamyawkhxngwngrxbidodytrng imcaepntxngilkhnhainladbyxyxikkhrngtwxyangkarichngancakrup hakerimedincakcud 2 camiesnthangkaredindngni 2 0 6 3 1 6 3 phbwakarwnsanimiwngrxb enuxngcakmikaredinthangsainesnthangedim khux 6 3 1 sungkhntxnwithikhxngebrnthmikhwamsamarthinkartrwcsxbkarmiwngcrechnniidnnexngkarxthibaykhntxnwithikarthangankhxngkhntxnwithikhxngebrnth erimtnodykarkahndtwwnsa 2 twkhux kratay aela eta yunxyuthicuderimtn hlngcaknnih kratay edinipthilakawtamesnthang aelacathakarekhluxnyay eta mataaehnngediywkb kratay emuxthungewlathikahnd odyhak kratay edinipidthungcudcbkhxngraykaroyng nnaesdngwa immiwngrxb aethak kratay edinipecx eta aesdngwa miwngrxbFlow Chart rhsethiymaesdngkarthangantortoise 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 harekarwiekhraahkhwamsbsxnechingewlasahrbkhntxnwithikhxngebrnthnn camiprasiththiphaphinkarthanganethakbkhntxnwithitrwcsxbkarmiwngrxbkhxngflxyd Floyd s Tortoise and the Hare algorithm khux O l m ody m khux khwamyawkhxngthangedincakcuderimtn ipyngwngrxb Cycle thimi l cudyxd aetinkhwamepncringaelw khntxnwithitrwcsxbkarmiwngrxbkhxngebrnth ichewlainkarthanganechliyerwkwakhntxnwithitrwcsxbkarmiwngrxbkhxngflxydpraman 36 sungmiphlthaihprasiththiphaphkarthangankhxng khntxnwithiorhkhxngphxllard Pollard rho algorithm ephimkhunpraman 24 xikdwykhntxnwithithiekiywkhxngkhntxnwithitrwcsxbkarmiwngrxbkhxngflxyd Floyd s cycle finding algorithm khntxnwithiorhkhxngphxllard Pollard rho algorithm xangxingBrent s cycle detection algorithm Algorithmic cryptanalysis Antoine Joux Chapman amp Hall CRC Taylor amp Francis Group 2009 P 266 http lab iisec ac jp labs tanaka publications pdf conference conference 86 02 pdf lingkesiy 1980 PDF BIT 20 2 176 184 doi 10 1007 BF01933190 khlngkhxmulekaekbcakaehlngedim PDF emux 2009 09 24 subkhnemux 2011 09 15