การวิเคราะห์บิ๊กโอ

การคำนวณเวลาในการประมวลผลของโปรแกรมที่เป็นมาตรฐาน กลางจึงจะไม่คำนวณเป็นหน่วยวินาที แต่จะคำนวณโดยใช้ฟังก์ชันที่แปรผันกับจำนวนข้อมูล n ที่ ป้อนเข้าไป

กำหนดให้โปรแกรมใด ๆ ใช้เวลาในการประมวลผล T(n)
T(n) = ค่าคงที่ x n
T(n) = c*n
โดยที่ c เป็นค่าคงที่ และ n เป็นจำนวนข้อมูลที่โปรแกรมต้องประมวลผล

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

สัญลักษณ์บิ๊กโอ (Big-Oh Notation)

เราสามารถนำเสนอฟังก์ชันแสดงประสิทธิภาพเชิงเวลาให้อยู่ในรูปแบบที่ง่ายขึ้นโดยใช้ สัญลักษณ์ บิ๊กโอ O( ) เป็นตัวประมาณการประสิทธิภาพเชิงเวลาแทน T( ) โดยค่าคงที่ซึ่งปรากฏใน T( ) จะไม่ถูก น ามาพิจารณาใน O( ) ด้วย

ความสัมพันธ์ระหว่าง T( ) และ O( )

เมื่อ T(n) มีบิ๊กโอเป็น O(f(n)) แสดงว่า f(n) คือ ส่วนของ T(n) ที่ส่งผลต่อเวลาการท างานของ โปรแกรมมากที่สุดเมื่อค่า n มีขนาดใหญ่ ดังนั้นจึงกำหนดความสัมพันธ์ระหว่าง T( ) และ O( ) ได้ว่า ให้ n0 > 0 และค่าคงที่ c > 0 T(n) มีบิ๊กโอเป็น O(f(n)) เมื่อ T(n) ≤ c * f(n) ส าหรับจำนวนเต็มบวก n ≥ n0