วัตถุประสงค์หลักของวิชานี้ คือ ความสามารถในการออกแบบอัลกอริทึมเพื่อแก้ปัญหาตามข้อกำหนดได้ และต้องเป็นอัลกอริทึมที่มีประสิทธิภาพดีด้วย บทนี้ขอนำเสนอเรื่องการวิเคราะห์เพื่อให้รู้ถึงประสิทธิภาพของอัลกอริทึมที่เราได้ออกแบบไว้ โดยจะขอเน้มเฉพาะประสิทธิภาพเชิงเวลาการทำงานเป็นหลัก การวิเคราะห์เชิงเวลาการทำงานก็คือ การหา
ความสัมพันธ์ของเวลาการทำงานของอัลกอริทึมกับปริมาณข้อมูลขาเข้าที่นำไปประมวล
ผลโดยทั่วไป เมื่อข้อมูลขาเข้ามีปริมาณมากขึ้น ย่อมต้องใช้เวลาแก้ปัญหาการทำงานมากขึ้น
ตาม แต่จะมากขึ้นแค่ไหน เท่าไร เป็นสิ่งเราจะสนใจในบทนี้ โดยจะใช้วิธีการวิเคราะห์
อัลกอริทึมเชิงเส้นกำกับ ที่ง่าย และเพียงพอต่อการนำไปใช้เปรียบเทียบอัลกอริทึม
การแบ่งแยกและเอาชนะ
บทนี้นำเสนอกลวิธีการออกแบบอัลกอริทึมที่เรียกว่า การแบ่งแยกและเอาชนะ
(divide and conquer) กลวิธีนี้มีใช้เพื่อจัดการกับปัญหาในหลากหลายศาสตร์ ซึ่งก็ใช้ได้ดีทีเดียวกับการออกแบบอัลกอริทึม เพื่อแก้ไขปัญหาเชิงคำนวณ แนวคิดการแก้ปัญหาแบบนี้มีหลักการว่า แทนที่เราจะไปหาคำตอบของปัญหาใหญ่ปัญหาหนึ่งทีเดียวเลย อาจไม่สะดวกนัก สู้เราแบ่งปัญหาใหญ่นั้นออกเป็นปัญหาย่อยๆ หลาย ๆ ปัญหาที่มีขนาดเล็กกว่า หาคำตอบของแต่ละปัญหาย่อย แล้วนำคำตอบย่อยๆ ที่ได้นี้มารวมกันเพื่อกลายเป็นคำตอบของปัญหาใหญ่ อาจจะซับซ้อนน้อยกว่า และใช้เวลาโดยรวมที่ดีกว่าก็ได้ อัลกอริทึมแบบแบ่งแยกและเอาชนะมักมีประสิทธิภาพที่ดีกว่าอัลกอริทึมที่ทำงานอย่างตรงไปตรงมา ค่อยเป็นค่อยไป นอกจากนี้ยังเขียนบรรยายตัวอัลกอริทึมในรูปของการทำซ้ำแบบเรียกซ้ำได้อย่างเหมาะมาก ทำให้เขียนบรรยายอัลกอริทึมได้อย่างไม่ซับซ้อน และวิเคราะห์ประสิทธิภาพการทำงานได้ง่าย
ไม่มีความคิดเห็น:
แสดงความคิดเห็น