อ่าน 1 นาที
การวิเคราะห์เชิงความน่าจะเป็นของอัลกอริทึม
ในการวิเคราะห์อัลกอริทึมการวิเคราะห์เชิงความน่าจะเป็นของอัลกอริทึมเป็นแนวทางหนึ่งในการประเมินความซับซ้อนในการคำนวณของอัลกอริทึมหรือปัญหาการคำนวณ
การวิเคราะห์เชิงความน่าจะเป็นของอัลกอริทึม
ในการวิเคราะห์อัลกอริทึมการวิเคราะห์เชิงความน่าจะเป็นของอัลกอริทึมเป็นแนวทางหนึ่งในการประเมินความซับซ้อนในการคำนวณของอัลกอริทึมหรือปัญหาการคำนวณ โดยเริ่มต้นจากสมมติฐานเกี่ยวกับการกระจายความน่าจะเป็นบนเซตของอินพุตที่เป็นไปได้ทั้งหมด จากนั้นจึงใช้สมมติฐานนี้ในการออกแบบอัลกอริทึมที่มีประสิทธิภาพ หรือเพื่อหาความซับซ้อนของอัลกอริทึมที่ทราบอยู่แล้ว แนวทางนี้ไม่เหมือนกับแนวทางของอัลกอริทึมเชิงความน่าจะเป็นแต่สามารถนำมาใช้ร่วมกันได้
สำหรับอัลกอริธึมที่ไม่ใช้ความน่าจะเป็น โดยเฉพาะอย่างยิ่ง อัลกอริธึมเชิงกำหนด ประเภทของการประมาณความซับซ้อนเชิงความน่าจะเป็นที่พบได้บ่อยที่สุดคือความซับซ้อนในกรณีเฉลี่ย และความซับซ้อนเกือบตลอดเวลา ในการหาความซับซ้อนในกรณีเฉลี่ย เมื่อกำหนดการกระจายของข้อมูลป้อนเข้าแล้ว จะมีการประเมินเวลาที่คาดหวังของอัลกอริธึม ในขณะที่สำหรับการประมาณความซับซ้อนเกือบตลอดเวลา จะมีการประเมินว่าอัลกอริธึมยอมรับการประมาณความซับซ้อนที่กำหนดซึ่งเกือบจะแน่นอนหรือไม่
ในการวิเคราะห์เชิงความน่าจะเป็นของอัลกอริธึมเชิงความน่าจะเป็น (แบบสุ่ม) นอกจากข้อมูลป้อนเข้าแล้ว ยังต้องพิจารณาถึงการกระจายหรือค่าเฉลี่ยของตัวเลือกที่เป็นไปได้ทั้งหมดในแต่ละขั้นตอนแบบสุ่มด้วย
ดูเพิ่มเติม
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ การวิเคราะห์เชิงความน่าจะเป็นของอัลกอริทึม
ในการวิเคราะห์อัลกอริทึมการวิเคราะห์เชิงความน่าจะเป็นของอัลกอริทึมเป็นแนวทางหนึ่งในการประเมินความซับซ้อนในการคำนวณของอัลกอริทึมหรือปัญหาการคำนวณ
ดูเพิ่มเติม
การวิเคราะห์แบบตัดจำหน่าย ความซับซ้อนในกรณีเฉลี่ย กรณีที่ดีที่สุด กรณีที่แย่ที่สุด และกรณีเฉลี่ย การลดตัวเองแบบสุ่ม หลักการตัดสินใจแบบเลื่อนออกไป ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?