ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบบสุ่ม"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข |
ไม่มีความย่อการแก้ไข |
||
บรรทัด 5:
ตัวอย่าง ลองพิจารณาการหาตัวอักษร a ใน[[อาร์เรย์]]ขนาด ''n'' เมื่อสมมุติว่าครึ่งหนึ่งในอาร์เรย์นี้เป็น a และอีกครึ่งหนึ่งเป็น b วิธีที่เห็นชัดวิธีหนึ่งคือการดูแต่ละตัวในอาร์เรย์ แต่วิธีนี้อาจทำให้ต้องดูถึง n/2 ตัวในกรณีที่แย่ที่สุด (นั่นคือครึ่งแรกของอาร์เรย์เป็น b ทั้งหมด) การพยายามแก้ไขเหตุการณ์นี้โดยเปลี่ยนลำดับการดู เช่น อ่านจากหลังมาหน้า หรืออ่านตัวเว้นตัว ก็ไม่ได้ช่วยให้อะไรดีขึ้นเลย ที่จริงแล้ว วิธีการใดก็ตามที่ลำดับของการตรวจสอบสมาชิกแต่ละตัวถูกกำหนดไว้ตายตัวแล้ว (นั่นคือ เป็นอัลกอริทึม''ดิเทอร์มินิสติก'') เราจะไม่สามารถรับประกันได้เลยว่าอัลกอริทึมจะทำงานสำเร็จอย่างรวดเร็ว ใน''ทุกๆอินพุทที่เป็นไปได้'' แต่ถ้าหากเราตรวจสอบสมาชิกในอาร์เรย์แบบสุ่ม(ไม่มีลำดับที่แน่นอน) ''มีความน่าจะเป็นสูง''ที่เราจะสามารถหา a พบในเวลาอันรวดเร็ว ''ไม่ว่าอินพุทจะเป็นเช่นไรก็ตาม''
ลองจินตนาการว่าเราจะต้องเผชิญหน้ากับ "ผู้ประสงค์ร้าย" ที่เก่งกาจอย่างคาดไม่ถึง กล่าวคือ คนๆนี้สามารถล่วงรู้วิธีการในการจัดการกับปัญหาของอัลกอริทึม และสามารถหาอินพุทที่แย่ที่สุดมาทำให้อัลกอริทึมทำงานได้ประสิทธิภาพไม่ดีได้เสมอ(ดู[[การวิเคราะห์เชิงแข่งขัน]]) อย่างไรก็ตามผู้ประสงค์ร้ายคนนี้จะสามารถทำร้ายอัลกอริทึมของเราได้น้อยลง หากอัลกอริทึมไม่ได้มีพฤติกรรมที่แน่นอน (ทำให้ผู้ประสงค์ร้ายไม่สามารถเดาได้ถูก) ด้วยเหตุผลเดียวกันนี้เองที่ทำให้ [[การสุ่ม]] เป็นที่แพร่หลายใน[[วิทยาการเข้ารหัสลับ]] ในงานประยุกต์ทางด้านการเข้ารหัสลับนั้น ตัวเลขสุ่มเทียมไม่สามารถนำมาใช้ได้ เนื่องจากผู้ประสงค์ร้ายสามารถทายเลขนี้ได้ ทำให้อัลกอริทึมมีลักษณะเป็นแบบดิเทอร์มินิสติกดีๆเท่านั้นเอง ดังนั้นจึงจำเป็นต้องมีแหล่งกำเนิดที่สามารถสร้างเลขสุ่มที่แท้จริงได้ หรือไม่ก็ต้องมี''ตัวสร้างตัวเลขสุ่มเทียมที่มีความปลอดภัยในการเข้ารหัสลับ'' อีกศาสตร์หนึ่งที่การสุ่มได้หยั่งรากฝังลึกเข้าไปคือ[[คอมพิวเตอร์ควอนตัม]]([[:en:quantum computer|quantum computer]])
==แหล่งอ้างอิง==
| |||