ขั้นตอนวิธีแบบสุ่ม

เวลาที่ใช้ในการทำงาน

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

ควิกซอร์ต

ควิกซอร์ต น่าจะเป็นขั้นตอนวิธีที่ใช้จริงที่เราคุ้นเคยที่สุดที่ใช้การสุ่มอย่างได้ผลดีมากๆ ขั้นตอนวิธีนี้ในแบบที่เป็นดิเทอร์มินิสติกต้องใช้เวลา 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⁻² ดังนั้นหากเราให้มันทำงาน n²log (n) รอบ และเลือกผลลัพธ์ที่มีค่าน้อยที่สุด เราก็จะสามารถหาการตัดที่น้อยที่สุดได้ด้วยความน่าจะเป็นสูง