ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบบสุ่ม"

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Nullzerobot (คุย | ส่วนร่วม)
เก็บกวาด
Nullzerobot (คุย | ส่วนร่วม)
เก็บกวาด
บรรทัด 44:
ออกจาก G
 
ให้ ''n = |V[G]|''
สามารถแสดงได้ว่า ขั้นตอนวิธีนี้ให้ผลเป็นการตัดที่น้อยที่สุด ด้วยความน่าจะเป็นอย่างน้อย ''n<sup>-2</sup>''
ดังนั้นหากเราให้มันทำงาน ''n<sup>2</sup>log (n) '' รอบ และเลือกผลลัพธ์ที่มีค่าน้อยที่สุด