บทนำเชิงภาพเกี่ยวกับสัญกรณ์ Big O

• สัญกรณ์ Big O ใช้แสดงประสิทธิภาพของฟังก์ชันในรูปแบบของ แนวโน้มการเติบโตตามการเปลี่ยนแปลงของขนาดอินพุต
• บทความนี้อธิบาย Big O ประเภทหลักอย่าง ค่าคงที่, ลอการิทึม, เชิงเส้น, และ กำลังสอง พร้อมตัวอย่างประกอบ
• ความซับซ้อนเชิงเวลา แตกต่างกันไปตามโครงสร้างข้อมูลและอัลกอริทึม และเห็นความต่างได้จากงานอย่างการเรียงลำดับอาร์เรย์หรือการค้นหา
• การปรับปรุงประสิทธิภาพของโค้ดจริงให้ดีขึ้นนั้น หัวใจสำคัญคือ การเลือกโครงสร้างข้อมูลที่เหมาะสม และการตัดการคำนวณที่ไม่จำเป็นภายในลูป
• Big O จะแสดง ความสัมพันธ์ระหว่างอินพุตกับเวลาในการทำงาน ในรูปแบบที่เรียบง่ายที่สุดเสมอ และเมื่อปรับปรุงประสิทธิภาพ ควรวัดผลจากโค้ดจริงโดยตรง

---

ภาพรวมของสัญกรณ์ Big O

• สัญกรณ์ Big O คือวิธีอธิบาย แนวโน้มการเติบโตของเวลาในการทำงานตามขนาดอินพุต (n) แทนการวัดเวลาโดยตรง
• มันจัดประเภทเวลาในการทำงานของฟังก์ชันตามขนาดอินพุต โดยรูปแบบที่มักนำมาวิเคราะห์คือ ค่าคงที่ (O(1)), ลอการิทึม (O(log n)), เชิงเส้น (O(n)), และ กำลังสอง (O(n²))
• บทความนี้อธิบายแนวคิดของแต่ละประเภท พร้อมตัวอย่างเชิงภาพและตัวอย่างโค้ดจริง เพื่อให้แม้แต่มือใหม่ก็เข้าใจได้

การวนซ้ำ (Iterating) และอัลกอริทึมเชิงเส้น

• ฟังก์ชัน sum(n) เป็นตัวอย่างของโครงสร้างการวนซ้ำที่บวกค่าตั้งแต่ 1 ถึง n ซึ่งเมื่อค่าอินพุต n เพิ่มขึ้น เวลาในการทำงานก็ เพิ่มขึ้นแบบแปรผันตรง
• ในทางปฏิบัติ sum(1e9) ใช้เวลาประมาณ 1 วินาที และ sum(2e9) ใช้เวลาประมาณ 2 วินาที ทำให้เวลาแบบนาฬิกาจริง (wall-clock time) เติบโตตามรูปแบบ O(n)
• ความซับซ้อนเชิงเวลา คือความสัมพันธ์ระหว่างอินพุตของฟังก์ชันกับเวลาในการทำงาน และแสดงด้วย สัญกรณ์ Big O (O(n) — แปรผันตาม n)
• หากใช้สูตรคณิตศาสตร์แทนการวนซ้ำ เช่น sum(n) = (n*(n+1))/2 เวลาในการทำงานจะ คงที่โดยไม่ขึ้นกับค่าอินพุต n
• ฟังก์ชันแบบนี้เรียกว่า ความซับซ้อนเชิงเวลาคงที่ O(1) ซึ่งมีลักษณะเด่นคือเวลาในการทำงานไม่เติบโตตามการเปลี่ยนแปลงของอินพุต

ไวยากรณ์ของสัญกรณ์ Big O

• O ใน Big O มาจากคำว่า “Order (ลำดับการเติบโต)” และใช้เพื่อ แสดงเฉพาะรูปแบบการเติบโตเท่านั้น
• มันไม่ได้แสดงค่าจริงสัมบูรณ์ของเวลาในการทำงาน แต่ เขียนเฉพาะ 'รูปแบบ' ของการเติบโตเมื่อเทียบกับอินพุตอย่างกระชับ
• ตัวอย่างเช่น แม้จะเป็นฟังก์ชัน O(n) ก็จะไม่เขียนซับซ้อนเป็น 'O(2n)' หรือ 'O(n+1)' แต่จะ เลือกเฉพาะพจน์ที่เรียบง่ายที่สุด

การลดเวลาโดยอาศัยการจัดรูปแบบอินพุต

• เช่นในตัวอย่างสูตร sum(n) เราสามารถ ปรับปรุงอัลกอริทึมให้ความซับซ้อนเชิงเวลาเปลี่ยนจาก O(n) เป็น O(1) ได้
• อย่างไรก็ตาม ความซับซ้อนเชิงเวลาคงที่ไม่ได้แปลว่าจะเร็วกว่าเสมอไป เพราะเวลาในการทำงานจริงยังต่างกันได้ตามประเภทของการคำนวณ
• อัลกอริทึม O(n) อาจเร็วกว่า O(1) ในอินพุตบางแบบ แต่เมื่อขนาดอินพุตใหญ่ขึ้น วิธีแบบ O(1) จะได้เปรียบเสมอ

การเรียงลำดับ (Sorting) และอัลกอริทึมกำลังสอง (Quadratic): ตัวอย่าง Bubble Sort

• Bubble Sort เป็นตัวอย่างพื้นฐานของการเรียงอาร์เรย์ด้วยการสลับค่าที่อยู่ติดกันซ้ำไปเรื่อย ๆ
• หากเรียงอยู่แล้ว อาจวนเพียง 1 รอบ (O(n)) แต่ถ้าเรียงย้อนลำดับ ต้องไล่วนประมาณ n รอบซ้ำ ๆ → กรณีแย่ที่สุด จำนวนการทำงานรวมเป็น n²
• อัลกอริทึม O(n²) จะมีเวลาในการทำงานเพิ่มขึ้นอย่างมากในลักษณะกำลังสองเมื่ออินพุตมีขนาดใหญ่ขึ้น
• ในการใช้งานจริง Big O มักอิงจาก กรณีแย่ที่สุด (worst-case) เสมอ (แม้บางครั้งจะมีการระบุกรณีเฉลี่ยหรือกรณีดีที่สุดด้วย)
• แม้จำนวนรอบการวนจะลดลงได้ตามสถานะเริ่มต้นของอาร์เรย์ แต่เมื่อพิจารณากรณีแย่ที่สุด ก็ยัง ถูกจัดเป็นความซับซ้อนเชิงเวลากำลังสอง

การค้นหา (Searching) และอัลกอริทึมลอการิทึม: ตัวอย่าง Binary Search

• Binary Search จะประเมินค่ากลางของช่วงที่เรียงลำดับแล้ว และตัดพื้นที่ของคำตอบทิ้งไปครึ่งหนึ่งในแต่ละขั้น
• ตัวอย่างเช่น การเดาเลขหนึ่งค่าระหว่าง 1~100 ใช้มากสุด 7 ครั้ง และแม้เป็นช่วง 1~1 พันล้าน ก็ยังใช้ไม่ถึง 31 ครั้ง
• เพราะรายชื่อผู้สมัครคำตอบถูกลดลงครึ่งหนึ่งทุกขั้น เวลาในการทำงานจึงเป็น O(log n) (ความซับซ้อนเชิงเวลาลอการิทึม)
• อัลกอริทึมแบบลอการิทึมจะเพิ่มขึ้นช้ามากเมื่อ n ใหญ่ขึ้น (มีประสิทธิภาพสูงกว่าทั้งแบบเชิงเส้นและกำลังสองอย่างชัดเจน)
• เมื่อเทียบกราฟการเติบโต จะเห็นความต่างระหว่าง log n, n และ n² ได้อย่างเด่นชัด

การประยุกต์ใช้จริง: เคล็ดลับปรับปรุงความซับซ้อนเชิงเวลา

การค้นหารายการในลิสต์

• โดยพื้นฐานแล้ว ฟังก์ชันค้นหาค่าในอาร์เรย์จะเป็น O(n)
• หากมีการค้นหาบ่อยครั้ง การใช้โครงสร้างข้อมูลอย่าง Set จะช่วยปรับปรุงเป็น O(1) ได้
• อย่างไรก็ตาม กระบวนการแปลงด้วย new Set(array) เองก็มีต้นทุน O(n) จึงเหมาะเมื่อมีการค้นหาซ้ำบ่อย ๆ เท่านั้น (ต้องคำนึงถึงต้นทุนการแปลงด้วย)
• ตัวอย่าง: items.has("banana") ให้ความซับซ้อนเชิงเวลาคงที่

การเขียนลูปโดยใช้ดัชนี

• โค้ดที่เรียก .indexOf ภายในลูปแบบด้านล่างนี้ มักเป็นสาเหตุของปัญหาด้านประสิทธิภาพ

  function buildList(items) {
    const output = [];
    for (const item of items) {
      const index = items.indexOf(item);
      output.push(`Item ${index + 1}: ${item}`);
    }
    return output.join("\n");
  }
  

• เนื่องจาก .indexOf เป็นการทำงานแบบ O(n) เมื่ออยู่ในลูป จึงทำให้โดยรวมกลายเป็นรูปแบบ O(n^2)

• หากใช้การวนแบบอิงดัชนี หรือใช้ forEach((item, index) => ...) จะปรับปรุงเป็น O(n) ได้

  function buildList(items) {
    const output = [];
    for (let i = 0; i < items.length; i++) {
      output.push(`Item ${i + 1}: ${items[i]}`);
    }
    return output.join("\n");
  }
  

การใช้ Memoization

• โครงสร้างที่มีการคำนวณซ้ำเมื่อถูกเรียกหลายครั้ง เช่น factorial สามารถปรับปรุงประสิทธิภาพได้ด้วย การแคชผลลัพธ์ (ใช้ Map)

• การค้นหาใน Map เป็น O(1) จึงช่วยลดการคำนวณซ้ำที่ไม่จำเป็น

• อย่างไรก็ตาม การแคชช่วยปรับปรุงเวลาเฉลี่ย และแม้ ความซับซ้อนเชิงเวลาในกรณีแย่ที่สุดอาจไม่เปลี่ยน แต่ก็ช่วยเพิ่มประสิทธิภาพในการทำงานจริงได้

  const cache = new Map();
  function factorial(n) {
    if (cache.has(n)) {
      return cache.get(n);
    }
    if (n === 0) {
      return 1;
    }
    const result = n * factorial(n - 1);
    cache.set(n, result);
    return result;
  }
  

การประเมินประสิทธิภาพและบทสรุป

• เมื่อต้องการปรับปรุงประสิทธิภาพของโค้ด ควรตรวจสอบด้วย การทดสอบการรันจริง ควบคู่กับความซับซ้อนเชิงเวลาทางทฤษฎี เพื่อยืนยันว่าดีขึ้นจริง
• Big O แสดง ความสัมพันธ์และรูปแบบการเติบโต ระหว่างอินพุตกับเวลาในการทำงานในรูปแบบที่เรียบง่ายและเป็นแก่นที่สุด
• การเลือกอัลกอริทึมที่ดีและการปรับโครงสร้างข้อมูลให้เหมาะสม สามารถเพิ่มประสิทธิภาพของโค้ดได้สูงสุด

สรุปย่อ

• สัญกรณ์ Big O ใช้แสดงความสัมพันธ์ระหว่างค่าอินพุตของฟังก์ชันกับเวลาในการทำงาน
• ระดับประสิทธิภาพหลัก: O(1) (ค่าคงที่), O(log n) (ลอการิทึม), O(n) (เชิงเส้น), O(n^2) (กำลังสอง)
• หากต้องการเขียนโค้ดอย่างมีประสิทธิภาพ การเลือกอัลกอริทึมที่เหมาะสมและการปรับลูปให้เหมาะสม เป็นสิ่งสำคัญ
• ควรวัดประสิทธิภาพจริงโดยตรงเพื่อยืนยันว่าการปรับปรุงได้ผล
• สามารถใช้กราฟเปรียบเทียบรูปแบบการเติบโตเพื่อมองเห็นลักษณะของความซับซ้อนเชิงเวลาได้อย่างชัดเจน