เมนูนำทาง
ขั้นตอนวิธีของเฮิร์ชเบิร์ก ข้อมูลขั้นตอนวิธีขั้นตอนวิธีของเฮิร์ชเบิร์กเป็นขั้นตอนวิธีที่ใช้ในการหาการจัดเรียงของลำดับสายอักขระที่ดีที่สุด สมมติว่าให้ x และ y เป็นสายอักขระซึ่ง n เป็นความยาวของสายอักขระ x และ m เป็นความยาวของสายอักขระ y เราสามารถใช้ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์ (Needleman – Wunsch algorithm) หาการจัดเรียงที่ดีที่สุดได้โดยใช้เวลา O(nm) และใช้เนื้อที่ O(nm) แต่หากเราใช้ขั้นตอนวิธีของเฮิร์ชเบิร์กซึ่งดีกว่าขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์เราจะหาการจัดเรียงที่ดีที่สุดภายในเวลา O(nm) และใช้เนื้อที่เพียง O(min{n,m})[3]
เมนูนำทาง
ขั้นตอนวิธีของเฮิร์ชเบิร์ก ข้อมูลขั้นตอนวิธีใกล้เคียง
แหล่งที่มา
WikiPedia: ขั้นตอนวิธีของเฮิร์ชเบิร์ก http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dy... http://www.cs.toronto.edu/~brudno/csc2427/Lec7Note... http://www.cs.tau.ac.il/~rshamir/algmb/98/scribe/h... http://www.csci.agh.edu.pl/42/