Big-O Notation (สรุปด่วน)

Big-O คือสัญลักษณ์ที่ใช้บอก "กรณีที่แย่ที่สุด (Worst-Case)" ของระยะเวลา (Time) หรือหน่วยความจำ (Space) ที่อัลกอริทึมต้องใช้เมื่อข้อมูล (n) มีขนาดใหญ่ขึ้น

อัตราการเติบโต (จากเร็วไปช้า)

1. O(1) - Constant: เร็วที่สุด ข้อมูลเยอะแค่ไหนก็ใช้เวลาเท่าเดิม (เช่น การเข้าถึง array[0], การอ่านค่าจาก Hash Map)
2. O(log n) - Logarithmic: ตัดข้อมูลทิ้งทีละครึ่ง (เช่น Binary Search, การค้นหาใน Binary Search Tree)
3. O(n) - Linear: แปรผันตรงกับจำนวนข้อมูล ต้องวนลูปดูทุกตัว (เช่น การหาค่า Max/Min ใน Array ที่ไม่ได้เรียง)
4. O(n log n) - Linearithmic: การเรียงลำดับที่มีประสิทธิภาพ (เช่น Merge Sort, Quick Sort)
5. O(n^2) - Quadratic: วนลูปซ้อนลูป (เช่น Bubble Sort, Insertion Sort, เทียบของทุกคู่)
6. O(2^n) - Exponential: แตกกิ่งก้านสาขาทุกกรณี (เช่น Recursive Fibonacci แบบไม่มี Memoization)
7. O(n!) - Factorial: ช้าที่สุด จัดเรียงสับเปลี่ยนทุกรูปแบบ (เช่น Traveling Salesman Problem แบบ Brute Force)

กฎการคำนวณง่ายๆ (Rules of Thumb)

• ตัดค่าคงที่ทิ้ง: O(2n + 5) -> O(n)
• สนใจเฉพาะตัวที่โตเร็วที่สุด: O(n^2 + n + log n) -> O(n^2)
• บวกกันเมื่อทำทีละขั้นตอน: Loop 2 รอบแยกกัน O(n) + O(n) = O(n)
• คูณกันเมื่อซ้อนทับกัน: Loop ซ้อนกัน O(n) * O(n) = O(n^2)