ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบบสุ่ม"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Octahedron80 (คุย | ส่วนร่วม) ล อัลกอริทึมแบบสุ่ม ถูกเปลี่ยนชื่อเป็น ขั้นตอนวิธีแบบสุ่ม |
Octahedron80 (คุย | ส่วนร่วม) ล แทนที่ "อัลกอริทึมแบบสุ่ม" → "ขั้นตอนวิธีแบบสุ่ม" +แทนที่ "อัลกอริทึม" → "ขั้นตอนวิธี"ด้วย[[WP:iScript |
||
บรรทัด 1:
{{ช่วยดูหน่อย}}
{{shortcut|[[randomized algorithm]]}}
'''
หากลองพิจารณาการหาตัวอักษร a ใน[[อาร์เรย์]]ขนาด ''n'' เมื่อสมมุติว่าครึ่งหนึ่งในอาร์เรย์นี้เป็น a และอีกครึ่งหนึ่งเป็น b วิธีที่เห็นชัดวิธีหนึ่งคือการดูแต่ละตัวในอาร์เรย์ แต่วิธีนี้อาจทำให้ต้องดูถึง n/2 ตัวในกรณีที่แย่ที่สุด (นั่นคือครึ่งแรกของอาร์เรย์เป็น b ทั้งหมด) การพยายามแก้ไขเหตุการณ์นี้โดยเปลี่ยนลำดับการดู เช่น อ่านจากหลังมาหน้า หรืออ่านตัวเว้นตัว ก็ไม่ได้ช่วยให้อะไรดีขึ้นเลย ที่จริงแล้ว วิธีการใดก็ตามที่ลำดับของการตรวจสอบสมาชิกแต่ละตัวถูกกำหนดไว้ตายตัวแล้ว (นั่นคือ เป็น
ลองจินตนาการว่าเราจะต้องเผชิญหน้ากับ "ผู้ประสงค์ร้าย" ที่เก่งกาจอย่างคาดไม่ถึง กล่าวคือ คนๆนี้สามารถล่วงรู้วิธีการในการจัดการกับปัญหาของ
ในตัวอย่างที่กล่าวมานี้
[[ทฤษฎีความซับซ้อนในการคำนวณ]]ซึ่งเป็นการศึกษาเกี่ยวกับทรัพยากรทางการคำนวณที่ต้องใช้ในการแก้ปัญหาหนึ่งๆ ได้สร้างแบบจำลองของ
ในประวัติศาสตร์
การตรวจสอบการเป็นจำนวนเฉพาะมิลเลอร์-ราบินนั้น มีหลักการพื้นฐานอยู่บนความสัมพันธ์ทวิภาค ระหว่างจำนวนเต็มบวกสองตัว k และ n ใดๆ ที่สามารถบอกได้ว่า ''k'' "เป็นตัวยืนยันการเป็นจำนวนประกอบของ" ''n'' เราสามารถแสดงได้ว่า
* ถ้ามีตัวยืนยันการเป็นจำนวนประกอบของ ''n'' แล้ว ''n'' เป็นจำนวนประกอบ (หมายความว่า ''n'' ไม่เป็น[[จำนวนเฉพาะ]]) และ
* ถ้า ''n'' เป็นจำนวนประกอบแล้ว มีอย่างน้อยสามในสี่ของจำนวนนับที่มีค่าน้อยกว่า ''n'' ที่เป็นตัวยืนยันการเป็นจำนวนประกอบของ ''n'' ได้ และ
* มี
สังเกตว่าข้อเท็จจริงเหล่านี้ทำให้สรุปได้ว่าปัญหาการทดสอบการเป็นจำนวนเฉพาะอยู่ในโค-อาร์พี
สมมุติ ''n'' เป็นจำนวนประกอบ ถ้าเราเลือกตัวเลขที่น้อยกว่า ''n'' มี 100 ตัว ความน่าจะเป็นที่จะหา "ตัวยืนยัน" ดังกล่าวไม่เจอจะเป็น (1/4)<sup>100</sup> ซึ่งในทางปฏิบัติแล้ววิธีนี้ก็เป็นการทดสอบการเป็นจำนวนเฉพาะที่ใช้ได้วิธีหนึ่ง และอาจจะไม่มีวิธีใดเลยที่ใช้ได้ดีในทางปฏิบัติเมื่อ ''n'' มีขนาดใหญ่มาก เราสามารถลดความน่าจะเป็นที่จะเกิดความผิดพลาดให้เหลือเท่าใดก็ได้ โดยการเพิ่มรอบการทำงานให้มากพอ
ดังนั้น ในทางปฏิบัติแล้ว จึงมักไม่ค่อยมีใครสนใจกับโอกาสเกิดความผิดพลาดที่มีเล็กน้อยนี้สักเท่าไร เพราะเราสามารถทำให้มันน้อยลงเท่าไรก็ได้ตามใจปรารถนา ที่จริงแล้ว ถึงแม้ว่าเราจะ[[การทดสอบการเป็นจำนวนเฉพาะของ AKS|มี]]
สมมุติว่าเราใช้วิธีเชิงสุ่ม แล้วมีความน่าจะเป็นที่จะเกิดความผิดพลาดเป็น 2<sup>−1000</sup> คำถามที่ตามมาคือ ตัวเลขนี้เกิดจาก[[การพิสูจน์ทางคณิตศาสตร์]]หรือไม่? ถึงแม้ว่าโอกาสผิดพลาดจะน้อยมากเมื่อเทียบกับโอกาสเกิดความผิดพลาดของฮาร์ดแวร์ที่ใช้ทำมัน หรือโอกาสที่คนตรวจบทพิสูจน์จะมองข้ามความผิดพลาดไป แต่จริงๆแล้วการบอกว่ามีความน่าจะเป็นน้อยนี้ ควรให้ความหมายว่าอย่างไรดี?
[[ควิกซอร์ต]] น่าจะเป็น
ตัวอย่างที่[[ซับซ้อน]]ขึ้นกว่าอีกหน่อย คือการใช้
หาการตัดน้อยสุด(กราฟไม่มีทิศทาง G) {
บรรทัด 42:
ให้ ''n = |V[G]|''
สามารถแสดงได้ว่า
ดังนั้นหากเราให้มันทำงาน ''n<sup>2</sup>log(n)'' รอบ และเลือกผลลัพธ์ที่มีค่าน้อยที่สุด
เราก็จะสามารถหาการตัดที่น้อยที่สุดได้ด้วยความน่าจะเป็นสูง
|