อัลกอริธึมแบบสุ่มเทียบกับแบบเรียกซ้ำ
อัลกอริธึมแบบสุ่มรวมความรู้สึกของการสุ่มไว้ในตรรกะของมันโดยการเลือกแบบสุ่มระหว่างการดำเนินการของอัลกอริธึม เนื่องจากการสุ่มนี้ พฤติกรรมของอัลกอริธึมสามารถเปลี่ยนแปลงได้แม้กระทั่งสำหรับอินพุตคงที่ สำหรับปัญหามากมาย อัลกอริธึมแบบสุ่มให้วิธีแก้ปัญหาที่ง่ายและมีประสิทธิภาพมากที่สุด อัลกอริธึมแบบเรียกซ้ำนั้นขึ้นอยู่กับแนวคิดที่ว่าสามารถค้นหาวิธีแก้ไขปัญหาได้โดยการค้นหาวิธีแก้ไขปัญหาย่อยที่เล็กกว่าของปัญหาเดียวกัน การเรียกซ้ำใช้กันอย่างแพร่หลายในการค้นหาวิธีแก้ไขปัญหาในวิทยาการคอมพิวเตอร์ และภาษาโปรแกรมระดับสูงจำนวนมากรองรับการเรียกซ้ำ
อัลกอริธึมแบบสุ่มคืออะไร
อัลกอริธึมแบบสุ่มรวมเอาความรู้สึกของการสุ่มโดยการเลือกแบบสุ่มที่ชี้นำการดำเนินการของอัลกอริธึม โดยทั่วไปจะทำได้โดยการนำชุดตัวเลขสุ่มที่สร้างโดยตัวสร้างตัวเลขสุ่มปลอมมาเป็นอินพุตเพิ่มเติม ด้วยเหตุนี้ พฤติกรรมของอัลกอริธึมอาจเปลี่ยนแปลงได้แม้จะเป็นอินพุตแบบตายตัวก็ตาม Quicksort เป็นอัลกอริธึมที่รู้จักกันอย่างแพร่หลายซึ่งใช้แนวคิดของการสุ่มและมีเวลาทำงานของ O(n log n) โดยไม่คำนึงถึงคุณสมบัติของอินพุต นอกจากนี้ วิธีการก่อสร้างแบบเพิ่มหน่วยแบบสุ่มจะใช้สำหรับโครงสร้างอาคาร เช่น ตัวเรือนูนในเรขาคณิตการคำนวณ ในวิธีนี้ จุดอินพุตจะถูกสุ่มเรียงสับเปลี่ยน จากนั้นจึงแทรกทีละจุดในโครงสร้าง การใช้อัลกอริธึมแบบสุ่มนั้นค่อนข้างง่ายกว่าการใช้อัลกอริธึมที่กำหนดขึ้นเองสำหรับปัญหาเดียวกัน ความท้าทายที่ใหญ่ที่สุดในการออกแบบอัลกอริธึมแบบสุ่มอยู่ในการดำเนินการวิเคราะห์เชิงซีมโทติกสำหรับความซับซ้อนของเวลาและอวกาศ
อัลกอริทึมแบบเรียกซ้ำคืออะไร
อัลกอริธึมแบบเรียกซ้ำมีพื้นฐานมาจากแนวคิดที่ว่าวิธีแก้ปัญหาสามารถพบได้โดยการค้นหาวิธีแก้ไขปัญหาย่อยที่เล็กกว่าของปัญหาเดียวกัน ในอัลกอริธึมแบบเรียกซ้ำ ฟังก์ชันถูกกำหนดในแง่ของเวอร์ชันก่อนหน้าของตัวเอง สิ่งสำคัญคือต้องสังเกตว่าการอ้างอิงตัวเองนี้ควรมีเงื่อนไขการยกเลิกเพื่อหลีกเลี่ยงการอ้างอิงตัวเองตลอดไป มีการตรวจสอบเงื่อนไขการยกเลิกก่อนอ้างอิงตัวเอง ขั้นตอนเริ่มต้นของอัลกอริธึมแบบเรียกซ้ำนั้นเกี่ยวข้องกับประโยคพื้นฐานของคำจำกัดความแบบเรียกซ้ำของปัญหา ขั้นตอนที่ทำตามขั้นตอนเริ่มต้นเกี่ยวข้องกับอนุประโยคอุปนัยของปัญหา อัลกอริธึมแบบเรียกซ้ำให้วิธีแก้ปัญหาที่ง่ายกว่าในหลาย ๆ สถานการณ์และใกล้เคียงกับวิธีคิดตามธรรมชาติมากกว่าอัลกอริธึมแบบวนซ้ำสำหรับปัญหาเดียวกัน แต่โดยทั่วไป อัลกอริธึมแบบเรียกซ้ำต้องการหน่วยความจำมากกว่าและมีราคาแพงในการคำนวณ
อัลกอริธึมแบบสุ่มและแบบเรียกซ้ำต่างกันอย่างไร
อัลกอริธึมแบบสุ่มคืออัลกอริธึมที่ใช้ความรู้สึกของการสุ่มโดยการเลือกแบบสุ่มที่อาจส่งผลต่อการทำงานของอัลกอริธึม ในขณะที่อัลกอริธึมแบบเรียกซ้ำเป็นอัลกอริธึมที่มีพื้นฐานมาจากแนวคิดที่ว่าสามารถค้นพบวิธีแก้ไขปัญหาได้ด้วยการค้นหา วิธีแก้ปัญหาย่อยที่เล็กกว่าของปัญหาเดียวกัน เนื่องจากการสุ่มในอัลกอริธึมแบบสุ่ม พฤติกรรมของอัลกอริธึมสามารถเปลี่ยนแปลงได้แม้สำหรับอินพุตเดียวกัน (ในการดำเนินการที่แตกต่างกันของอัลกอริธึม) แต่มันเป็นไปไม่ได้ในอัลกอริธึมแบบเรียกซ้ำและการทำงานของอัลกอริธึมแบบเรียกซ้ำจะเหมือนกันสำหรับอินพุตคงที่