ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบบสุ่ม"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ลไม่มีความย่อการแก้ไข |
เพิ่มเติม |
||
บรรทัด 12:
ในประวัตศาสตร์ อัลกอริทึมแบบสุ่มเริ่มเป็นที่รู้จัก จากการค้นพบของ[[การตรวจสอบการเป็นจำนวนเฉพาะมิลเลอร์-เรบิน|มิลเลอร์และเรบิน]]ในปี 1976 ว่า ปัญหา[[การตรวจสอบการเป็นจำนวนเฉพาะ]]ของตัวเลข สามารถแก้ได้อย่างมีประสิทธิภาพด้วยอัลกอริทึมแบบสุ่ม ในเวลานั้น ยังไม่มี[[อัลกอริทึมดิเทอร์มินิสติก]]สำหรับปัญหานี้เลย
การตรวจสอบการเป็นจำนวนเฉพาะมิลเลอร์-เรบินนั้น มีหลักการพื้นฐานอยู่บนความสัมพันธ์ทวิภาค ระหว่างจำนวนเต็มบวกสองตัว k และ n ใดๆที่สามารถบอกได้ว่า ''k'' "เป็นตัวยืนยันการเป็นจำนวนประกอบของ" ''n'' เราสามารถแสดงได้ว่า
* ถ้ามีตัวยืนยันการเป็นจำนวนประกอบของ ''n'' แล้ว ''n'' เป็นจำนวนประกอบ (หมายความว่า ''n'' ไม่เป็น[[จำนวนเฉพาะ]]) และ
* ถ้า ''n'' เป็นจำนวนประกอบแล้ว มีอย่างน้อยสามในสี่ของจำนวนนับที่มีค่าน้อยกว่า ''n'' ที่เป็นตัวยืนยันการเป็นจำนวนประกอบของ ''n'' ได้ และ
* มีอัลกอริทึมที่ทำงานได้รวดเร็วพอ ที่เมื่อให้ค่า ''k'' และค่า ''n'' อัลกอริทึมสามารถบอกได้ว่า ''k'' เป็นตัวยืนยันการเป็นจำนวนประกอบของ ''n'' หรือไม่
สังเกตว่าข้อเท็จจริงเหล่านี้ทำให้สรุปได้ว่าปัญหาการทดสอบการเป็นจำนวนเฉพาะอยู่ในโค-อาร์พี
สมมุติ ''n'' เป็นจำนวนประกอบ ถ้าเราเลือกตัวเลขที่น้อยกว่า ''n'' มี 100 ตัว ความน่าจะเป็นที่จะหา"ตัวยืนยัน"ดังกล่าไม่เจอจะเป็น (1/4)<sup>100</sup> ซึ่งในทางปฏิบัติแล้ววิธีนี้ก็เป็นการทดสอบการเป็นจำนวนเฉพาะที่ใช้ได้วิธีหนึ่ง และอาจจะไม่มีวิธีใดเลยที่ใช้ได้ดีในทางปฏิบัติเมื่อ ''n'' มีขนาดใหญ่มาก เราสามารถลดความน่าจะเป็นที่จะเกิดความผิดพลาดให้เหลือเท่าใดก็ได้ โดยการเพิ่มรอบการทำงานให้มากพอ
ดังนั้น ในทางปฏิบัติแล้ว จึงมักไม่ค่อยมีใครสนใจกับโอกาสเกิดความผิดพลาดที่มีเล็กน้อยนี้สักเท่าไร เพราะเราสามารถทำให้มันน้อยลงเท่าไรก็ได้ตามใจปรารถนา ที่จริงแล้ว ถึงแม้ว่าเราจะ[[การทดสอบการเป็นจำนวนเฉพาะของ AKS|มี]]อัลกอริทึมในการตรวจสอบการเป็นจำนวนเฉพาะแบบดิเทอร์มินิสติกที่สามารถทำงานได้ในเวลาโพลิโนเมียลแล้ว มันก็ยังไม่ได้ถูกนำไปใช้แทนวิธีเชิงความน่าจะเป็นแบบเดิมใน[[ซอฟท์แวร์]][[วิทยาการเข้ารหัสลับ|ด้านการเข้ารหัสลับ]] และก็ยังไม่มีใครคิดว่าจะเป็นเช่นนั้นได้ในอนาคตอันใกล้นี้ด้วย
สมมุติว่าเราใช้วิธีเชิงสุ่ม แล้วมีความน่าจะเป็นที่จะเกิดความผิดพลาดเป็น 2<sup>−1000</sup> คำถามที่ตามมาคือ ตัวเลขนี้เกิดจาก[[การพิสูจน์ทางคณิตศาสตร์]]หรือไม่? ถึงแม้ว่าโอกาสผิดพลาดจะน้อยมากเมื่อเทียบกับโอกาสเกิดความผิดพลาดของฮาร์ดแวร์ที่ใช้ทำมัน หรือโอกาสที่คนตรวจบทพิสูจน์จะมองข้ามความผิดพลาดไป แต่จริงๆแล้วการบอกว่ามีความน่าจะเป็นน้อยนี้ ควรให้ความหมายว่าอย่างไรดี?
If, using a randomized method, the probability of error is 2<sup>−1000</sup>, the philosophical question arises: is this a [[mathematical proof]]? After all, the probability of the algorithm's error is distinctly smaller than the probability of an error in the computer hardware executing it, or the reader making an error in reading a proof - what does it mean in real terms to consider this small a probability?
[[ควิกซอร์ต]] น่าจะเป็นอัลกอริทึมที่ใช้จริงที่เราคุ้นเคยที่สุดที่ใช้การสุ่มอย่างได้ผลดีมากๆ อัลกอริทึมนี้ในแบบที่เป็นดิเทอร์มินิสติกต้องใช้เวลา ''[[สัญกรณ์ Big O|O]](n^2)'' ในการเรียงเลข ''n'' ตัว สำหรับอินพุทบางรูปแบบ เช่น อาร์เรย์ที่ถูกเรียงมาอยู่แล้ว อย่างไรก็ตาม ถ้าอัลกอริทึมสลับตัวในอาร์เรย์แบบสุ่มก่อนที่จะเริ่มทำงาน มันจะมีความน่าจะเป็นสูงที่จะทำงานเสร็จในเวลา ''O(n log n)'' สำหรับอินพุททุกรูปแบบ ความแตกต่างระหว่างสองแบบนี้จะมีความสำคัญมาก เมื่อเราต้องจัดเรียงข้อมูลจำนวนมากๆ
==แหล่งอ้างอิง==
| |||