ในการเขียนโปรแกรมหรือการพัฒนาซอฟต์แวร์นั้น บ่อยครั้งที่โปรแกรมเมอร์มักจะโฟกัสหรือสนใจการเขียนโปรแกรมหรือพัฒนาระบบให้สามารถทำงานได้และตรงตามความต้องการของลูกค้าหรือผู้ใช้งาน โดยเฉพาะโปรแกรมเมอร์ที่อาจจะยังมีประสบการณ์น้อยหรือเป็นมือใหม่ ซึ่งบ่อยครั้งการที่เราต้องโฟกัสกับการพัฒนาระบบให้สามารถใช้งานได้ ตรงตามความต้องการและแล้วเสร็จภายในระยะเวลาที่กำหนดอาจจะทำให้เราลืมบางสิ่งบางอย่างไป นั้นคือรูปแบบและวิธีการเขียนของเราบ่อยครั้งที่ด้วยความรีบเร่งหรือสถานการณ์หลายๆอย่างทำให้เราเพียงแค่เขียนโปรแกรมเพื่อส่งโดยลืมเรื่องของ logic หรือความ clean ของ source code ของเรา ซึ่งกว่าเราจะรู้อีกทีก็ต่อเมื่อเราพัฒนาระบบไปมากแล้วหรือบางครั้งอาจจะมีการนำขึ้นใช้งานจริงไปแล้วและพบว่าโปรแกรมของเรามีความหน่วง หรือบางครั้งทำงานได้ช้า โดยเฉพาะเมื่อยิ่งใช้งานในระยะยาวและมีปริมาณข้อมูลจำนวนมาก ซึ่งหากเคยเจอสถานการณ์เช่นนี้ให้เราส่งสัยได้เลยว่า source code ของเราอาจจะเจอเข้ากับ Big O เข้าแล้ว แล้ว Big O คืออะไร?
Big O คืออะไร
Big O หรือที่เราเรียกกันเต็มๆว่า Big O Notation คือการที่โปรแกรมของเราต้องใช้ประสิทธิภาพและทรัพยากรอย่างมากไปกับ Algorithm ที่เราเขียนเพื่อให้ได้ผลลัพท์ตามที่เราต้องการ เช่น ให้เราลองนึกถึงภาพว่าหากมีข้อมูลรายการสั่งซื้อสินค้า 10,000 รายการที่ถูกเก็บในรูปแบบ Array ซึ่งเราจะต้องหาออเดอร์ๆ นึงที่เราต้องการด้วยการเขียน Loop for นั้นหมายความว่าระบบจะต้องวิ่งไล่หาเริ่มต้นจาก 1 ไปเรื่อยๆ หากโชคดีรายการที่เราค้นหาอยู่ลำดับต้นๆ ก็อาจจะใช้ทรัพยากรในการค้นหาไม่มาก แต่หากเป็นรายการท้ายๆ เราก็จะต้องใช้ทั้งเวลาและทรัพยากรจำนวนมากกว่าจะหาข้อมูลดังกว่าเจอ
ประเภทของ Big O มีอะไรบ้าง?
Big O นั้นแบ่งออกได้หลายประเภท ซึ่งแต่ละประเภทก็จะมีระดับการประมวลผลที่แตกต่างกันออกไป ซึ่งเราจะเรียกว่า Big O(n) โดย n เราจะใช้เป็นตัวแปรในการแทนประเภทหรือรูปแบบต่างๆ ของ Big O
1. O(1)
เป็น Algorithm หรือ Big O ที่ถือว่าดีที่สุดแล้วหากเทียบกับเพื่อนๆ ทั้งหมด โดยจะเป็นการใช้เวลาในการทำงานเพียงครั้งเดียวเสมอ เช่น จากโค้ดตัวอย่างจะเป็นการเช็คว่าเป็นเลขคู่หรือเลขคี่ ไม่ว่าเราจะใส่จำนวนตัวเลขที่ต้องการให้หาทั้งหมดเท่าไหร่ ก็จะทำแค่ mod ด้วย 2 ครั้งเดียวเท่านั้น
2. O(log n)
สำหรับ Big O ประเภทนี้ก็ยังถือว่าอยู่ในหมวด Big O ที่ยังดีอยู่ในระดับนึง เนื่องจากเป็นการทำงานที่จะลดจำนวน Loop ลงไปครึ่งนึงทุกๆครั้งที่ครบ Loop 1 รอบ ซึ่งจะช่วยลดจำนวนที่ไม่มีโอกาสเกิดขึ้นแน่ๆ ไปทีละครึ่ง
3. O(n)
สำหรับ Big O ประเภทนี้ก็ยังถือว่าอยู่ในกลุ่มที่ดีอยู่ เพราะจำนวนการทำงานหรือรอบของการทำงานจะอ้างอิงหรือขึ้นอยู่กับจำนวนค่าที่เรา input เข้าไป ตัวอย่างด้านล่างจะแสดงให้เห็นได้ชัดเจน คือการใส่ Loop 1 ชั้น
4. O(n log n)
Big O นี้หากจะให้อธิบายง่ายๆสั้นๆก็คือ เป็น Loop 2 ชั้นนั่นเอง โดยชั้นแรกจะเป็นลูปแบบ n รอบ และชั้นด้านในจะเป็นลูปที่ตัดจำนวนลดลงไปครึ่งนึง หรือมองให้เห็นภาพก็คือการนำ O(n) มารวมกับ O(log n) นั้นเอง
5. O(n^2)
สำหรับ Big O ประเภทนี้ถือว่าอยู่ในหมวดทีเริ่มแย่แล้ว เพราะเมื่อเราเพิ่มการ input ข้อมูลไป 2 เท่าระบบจะทำงานหนักขึ้นถึง 4 เท่าเลยทีเดียว
6. O(2^n)
สำหรับ Big O ประเภทนี้คือว่าเข้าขั้นหายนะแล้ว เพราะถือว่าเป็น Big O รองบอสเลยก็ว่าได้ ซึ่งถึงแม้ว่าจะเป็นการ input ข้อมูลเพียงนิดเดียวแต่กลับทำงานหรือประมวลผลหนักมาก หรือเรียกง่ายๆว่า เล่นใหญ่เกินเบอร์ เราจึงมักเรียก Big O นี้ว่า Exponential
7. O(n!)
สำหรับ Big O สุดท้ายนี้ ถือเป็นตัวแม่แห่งความหายนะเลยก็ว่าได้ เรียกได้ว่าเลวร้ายแบบสุดๆ และขอเตือนเลยว่าอย่าหาทำ เพราะจากตัวอย่างโค้ดด้านล่างจะเห็นเลยว่าเป็น Loop ที่ซ้อนกันเยอะๆ ชนิดที่เรียกได้ว่าเป็น factorial นั้นจึงเป็นชื่อหรือที่มาของ Big O นี้
ในส่วนของกราฟด้านล่างนี้จะเป็นกราฟที่ใช้อธิบายถึงระดับความเลวร้ายของ Big O เพื่อให้ท่านผู้อ่านมีความเข้าใจและเห็นภาพได้ชัดเจนมากขึ้นเกี่ยวกับผลกระทบและความรุนแรงของ Big O แต่ละประเภทครับ
Credit by https://pub.towardsai.net/big-o-notation-what-is-it-69cfd9d5f6b8