ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบบสุ่ม"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
เพิ่มเติม |
เพิ่มเติม-จบ |
||
บรรทัด 23:
สมมุติว่าเราใช้วิธีเชิงสุ่ม แล้วมีความน่าจะเป็นที่จะเกิดความผิดพลาดเป็น 2<sup>−1000</sup> คำถามที่ตามมาคือ ตัวเลขนี้เกิดจาก[[การพิสูจน์ทางคณิตศาสตร์]]หรือไม่? ถึงแม้ว่าโอกาสผิดพลาดจะน้อยมากเมื่อเทียบกับโอกาสเกิดความผิดพลาดของฮาร์ดแวร์ที่ใช้ทำมัน หรือโอกาสที่คนตรวจบทพิสูจน์จะมองข้ามความผิดพลาดไป แต่จริงๆแล้วการบอกว่ามีความน่าจะเป็นน้อยนี้ ควรให้ความหมายว่าอย่างไรดี?
[[ควิกซอร์ต]] น่าจะเป็นอัลกอริทึมที่ใช้จริงที่เราคุ้นเคยที่สุดที่ใช้การสุ่มอย่างได้ผลดีมากๆ อัลกอริทึมนี้ในแบบที่เป็นดิเทอร์มินิสติกต้องใช้เวลา ''[[สัญกรณ์ Big O|O]](n^2)'' ในการเรียงเลข ''n'' ตัว สำหรับอินพุทบางรูปแบบ เช่น อาร์เรย์ที่ถูกเรียงมาอยู่แล้ว อย่างไรก็ตาม ถ้าอัลกอริทึมสลับตัวในอาร์เรย์แบบสุ่มก่อนที่จะเริ่มทำงาน มันจะมีความน่าจะเป็นสูงที่จะทำงานเสร็จในเวลา ''O(n log n)'' สำหรับอินพุททุกรูปแบบ ความแตกต่างระหว่างสองแบบนี้จะมีความสำคัญมาก เมื่อเราต้องจัดเรียงข้อมูลจำนวนมากๆ
ตัวอย่างที่[[ซับซ้อน]]ขึ้นกว่าอีกหน่อย คือการใช้อัลกอริทึมเชิงสุ่มแก้ปัญหาทางด้าน[[ทฤษฎีกราฟ]] นี่คืออัลกอริทึมสำหรับแก้ปัญหา [[การตัดให้น้อยที่สุด]](minimum cut)
หาการตัดน้อยสุด(กราฟไม่มีทิศทาง G) {
ตราบใดที่ G ยังมี[[โหนด]]มากกว่า 2 โหนด ให้ทำ{
สุ่มเลือก[[เส้นเชื่อม]] (u,v) จาก G
หด(contract) เส้นเชื่อม โดยให้รักษาการมีเส้นเชื่อมหลายเส้น(multi-edge)เอาไว้
ลบ[[ลูป]]ทั้งหมดออก
}
ให้เส้นเชื่อมที่เหลืออยู่เป็นเอาท์พุท
}
ในที่นี้ การหดเส้นเชื่อม (u,v) หมายความถึง การเพิ่มโหนดขึ้นใหม่ (ให้ชื่อ w)
แล้วให้แทนทุกเส้นเชื่อม (u,x) และ (v,x) ด้วย (w,x) แล้วลบโหนด u และ v
ออกจาก G
ให้ ''n = |V[G]|''
สามารถแสดงได้ว่า อัลกอริทึมนี้ให้ผลเป็นการตัดที่น้อยที่สุด ด้วยความน่าจะเป็นอย่างน้อย ''n<sup>-2</sup>''
ดังนั้นหากเราให้มันทำงาน ''n<sup>2</sup>log(n)'' รอบ และเลือกผลลัพธ์ที่มีค่าน้อยที่สุด
เราก็จะสามารถหาการตัดที่น้อยที่สุดได้ด้วยความน่าจะเป็นสูง
==แหล่งอ้างอิง==
| |||