LewCPE's Blog

ว่ากันว่าสิ่งที่เอาชนะได้ยาก หรือดีไม่ดีอาจจะเอาชนะไม่ได้เลยก็คือเวลา  เวลาเป็นเครื่องบั่นทอนความสำเร็จได้มากที่สุดอย่างหนึ่งเท่าที่เราจะนึกอาจจะ

นานมาแล้วผมเคยอ่านหนังสือรบพิเศษ ในหนังสือเล่มนั้นรวบรวมหลักสูตรของบรรดานักรบหน่วยต่างๆ ที่ต้องการการฝึกไว้อย่างหนักเอาไว้ค่อนข้างครบ ที่น่าสนใจคือแนวทางการฝึกอย่างหนึ่งคือการยกเลิกเวลากลับบ้านโดยไม่บอกล่วงหน้า  เพื่อให้เหล่าผู้เข้ารับการฝึกท้อจนกว่าจะลาออกไป

น่าแปลกอย่างหนึ่งที่เวลาที่แน่นอนไม่ว่ามันจะนานเพียงใดก็ไม่ใช่อุปสรรคเท่าใดนัก ผมได้รู้จักกับหลายๆ คนที่รู้ตัวดีว่าจะเรียนโดยใช้เวลาเกินหลักสูตร และพบว่าเขาก็ไม่ได้ลำบากเดือนร้อนอะไร ว่ากันว่า Paul Erdős นักคณิตศาสตร์ชื่อก้องโลกเคยพนันกับเพื่อนของเขาว่าจะเลิกเสพยาที่ช่วยให้เขาทำงานได้วันละ 22 ชั่วโมงได้เป็นเวลาหนึ่งเดือน เพื่อพิสูจน์ว่าเขาไม่ได้ติดมัน แล้วเขาก็ชนะ

น่าสนใจมากว่าขณะเวลาที่แน่นอน ไม่ได้น่ากลัวอย่างที่คิด เวลาที่ไม่ได้เนิ่นนานอะไร หากแต่ดูเหมือนจะไม่มีจุดสิ้นสุดนั้นน่ากลัวยิ่งกว่า เรื่องนี้เราอาจจะ map เข้ากับการเรียนวิทยาศาสตร์คอมพิวเตอร์ได้ในรูปแบบของ Asymptotic Analysis ที่เราได้เห็นกันในหนังสือ Algorithm ในรูปแบบของ O-Notation ที่ตัดเอารายละเอียดออกไปแล้วมุ่งสนใจเฉพาะส่วนที่สำคัญที่สุด

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

โจทย์ที่ยากขึ้นไปเราอาจจะจัดให้อยู่ในคลาสอื่นๆ เช่น Class P เช่นเรากำลังเข้าใกล้คำตอบมากขึ้นเรื่อยๆ แต่ดูระยะทางแล้วช่างยาวไกล หรือหากยากมากๆ เราก็อาจจะจัดมันเป็น NP-hard ไป  ในกรณีแบบนี้เราอาจจะมองไม่เห็นคำตอบกันหรือไม่รู้ว่าเราเข้าใกล้มันรึยัง และแน่นอนว่าชีวิตจริงการแบ่งความยากของปัญหามันไม่ได้ง่ายๆ แบบสามสี่ขั้นเท่านั้น ปัญหาคณิตศาสตร์ก็เช่นเดียวกัน

ปล. ถ้าคุณไม่ได้เรียนสายคอม แล้วอ่านบล็อกเพ้อๆ นี่แล้วไม่รู้เรื่องก็อย่าแปลกใจ เพราะคนเขียนมันบ้าคอมพ์

ปล2. ถ้าคุณเรียนคอมแล้วอ่านไม่รู้เรื่องอยู่ดี ก็อย่าแปลกใจ เพราะคนเขียนมันเพ้อ