CoE KKU

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

ปัญหาการเลือก (selection problem): หาค่าที่มีค่ามากเป็นอันดับ k จากกลุ่มตัวเลข n ตัว

วิธีแรก: อ่านค่าทั้งหมดมาเก็บใน array แล้วทำการจัดเรียงจากค่ามากไปค่าน้อย ค่าที่ต้องการคือค่าที่อยู่ในตำแหน่ง k

อัลกอริทึมที่ดีกว่า: อ่านค่ามา k ตัวลงใน arrayแล้วทำการจัดเรียงจากค่ามากไปหาค่าน้อย จากนั้น อ่านค่าที่เหลือมาทีละค่า ถ้าค่าที่อ่านเข้ามานี้มีค่าน้อยกว่าค่าที่อยู่ที่ตำแหน่ง k ใน arrayก็ละทิ้งค่านั้นไป แต่ถ้ามันมีค่ามากกว่าค่าที่ตำแหน่ง k ใน array ก็บรรจุค่านั้นลงในตำแหน่งที่ถูกต้องตามลำดับของมันแล้วเอาค่าเดิมที่อยู่ในตำแหน่ง k ทิ้งไป เมื่อจบสิ้นการทำงานของอัลกอริทึมแล้ว ค่าที่อยู่ที่ตำแหน่ง k ก็คือคำตอบ

ดังนั้นโดยธรรมชาติแล้วก็จะเกิดคำถามขึ้น 2 คำถาม คือ

• อัลกอริทึมใดดีกว่ากัน และ
• อัลกอริทึมดังกล่าวนี้ดีพอหรือไม่

ประเด็นที่สำคัญ คือ ในหลายปัญหา การเขียนโปรแกรมที่เพียงแต่สามารถแก้ปัญหาเหล่านั้นได้ยังไม่เป็นการเพียงพอ ถ้าโปรแกรมนั้นจะต้องใช้ทำงานกับข้อมูลจำนวนมาก ๆ แล้วจะต้องคำนึงถึงเรื่องของ running time ด้วย ดังนั้น เราจะต้อง เรียนรู้การประเมิน running time ของโปรแกรมสำหรับอินพุตขนาดใหญ่ และที่สำคัญกว่า คือ เราสามารถเปรียบเทียบ running time ของโปรแกรมสองโปรแกรมโดยที่ไม่ต้องลงมือเขียนโปรแกรมจริงขึ้นมาก่อน