Asymptotic notation

         Asymptotic notation คือเครื่องหมายที่ใช้อธิบายการเติบโตของฟังก์ชันในการวิเคราะห์อัลกิริทึมจะนำเครื่องหมายนี้มาใช้ในการระบุประสิทธิภาพของอัลกริทึม โดยมีหลายสัญลักษณ์ดังนี้

1. Big-O Notation : O

        บิ๊ก-โอ ใช้ในการระบุทรัพยากรที่ใช้ในการทำงานของอัลกอริทึมเมื่อมีขนาดของอินพุทเปลี่ยนไป ปกติแล้วทรัพยากรดังกล่าวจะหมายถึงเวลานั่นคือ ความสัมพันธ์ระหว่าง เวลา กับ ขนาดของอินพุท หรืออินพุทที่ขนาดใดขนาดหนึ่ง เวลาที่ใช้ในการทำงานมากที่สุด (Upper bound) จะเป็นเท่าไร ซึ่งฟังก์ชันบิ๊ก-โอเป็นที่นิยมใช้มากที่สุดในการระบุประสิทธิภาพของอัลกอริทึม

ตัวอย่าง

        O(n) คือฟังก์ชันที่ใช้เวลาทำงานช้าที่สุด ≤ n เช่น อัลกอริทึม A มีประสิทธิภาพเป็น O(n2) ถ้า n = 10 แล้ว ฟังก์ชัน A จะใช้เวลาทำงานช้าที่สุด 100 หน่วยเวลา (อาจจะเร็วกว่า100ได้ แต่ช้าสุดไม่เกิน100) 

        จะเขียนได้ว่า f(n) є O(g(n)) เพื่อบอกว่า f(n) เป็นฟังก์ชันที่ไม่โตเร็วกว่า g(n)     
     

f(n) є O(g(n))

f(n) ≤ (g(n))

2. Big-Omega Notation : Ω

        โอเมก้าใหญ่ ใช้สำหรับบอกถึงเวลาที่ใช้น้อยที่สุดที่สุด (Lower bound) เมื่ออัลกอรึทึมนั้นๆทำงานกับอิพุทขนาดใดขนาดหนึ่ง

ตัวอย่าง

        Ω(n) คือฟังก์ชันที่ใช้เวลาทำงานเร็วที่สุด ≥ n เช่น อัลกอริทึ่ม A มีประสิทธิภาพเป็น Ω(n) ถ้า n = 10 แล้ว ฟังก์ชัน A จะใช้เวลาทำงานเร็วที่สุด 10 หน่วยเวลา (คือจะไม่เร็วไปกว่านี้ แต่อาจจะช้ากว่านี้ได้) จะเขียนได้ว่า f(n) є Ω(g(n)) เพื่อบอกว่า f(n) เป็นฟังก์ชันที่ไม่โตไม่ช้ากว่า g(n)

Cg(n) ≤ f(n)

3. Big-Teta Notation : Ө

        เทต้าใหญ่ ใช้สำหรับแสดงความสัมพันธ์ของเวลาการทำงาน f(n) = Ө(g(n)) ก็ต่อเมื่อ f(n) = O(g(n)) และ f(n) = Ω(g(n)) คือขอบบนและขอบล่างเป็นฟังก์ชันเดียวกัน

f(n) є Ө(g(n))

C1g(n) ≤ f(n) ≤ C2g(n)

รูปแสดงความสัมพันธ์ระหว่างเวลาที่ใช้กับจำนวนอินพุทของฟังก์ชัน 10n ฟังก์ชัน 5n+4 และ 3n

สังเกตได้ว่า ขอบบนกับขอบล่างเป็นฟังก์ชันเดียวกัน สัมประสิทธิ์ต่างกัน คือใช้เวลาการทำงาน = n

4. Little-o : o

        โอเล็ก คือฟังก์ชันที่ไม่แตะขอบบน นั่นคือฟังก์ชันนี้ทำงานช้าที่สุด ≤ n คือ o(g(n)) คือเซตของฟังก์ชันที่โตช้ากว่า g(n)

ตัวอย่าง หากเรามี t(n) = n0.98 + 0.05√n  เราสามารถเขียนได้เป็น O(n) หรือ o(n) แต่หากระบุเป็น Little-o จะเน้นให้เห็นชัดว่าไม่ถึง n  (เพราะค่ากำลังของ n คือ 1 แต่ในฟังก์ชั่น t(n) ค่ากำลังของ n คือ 0.98)

5. Little-omega : ω

        โอเมก้าเล็ก คือฟังก์ชันที่ไม่แตะขอบบนนั่นคือฟังก์ชันนี้จะทำงานเร็วที่สุด > n คือ ω(g(n)) คือเซตของฟังก์ชันที่โตเร็วกว่า g(n)

เปรีบเทียบลักษณะของฟังก์ชันแต่ละสัญลักษณ์

รูปการสรุปเชิงเปรียบเทียบ ลักษณะของฟังก์ชันของแต่ละสัญลักษณ์

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

1. exponential อยู่ในรูป an

2. polynomial  อยู่ในรูป na   (n ยกกำลังค่าคงที่) เช่น n3

3. Linear  อยู่ในรูป n
4. logarithmic  อยู่ในรูป logan

ทั้ง 4 รูปแบบจะมีอัตราการเติบโตเรียงจากมากไปหาน้อย an > na > n > logan 

อัตตราการเจริญเติบโตของฟังก์ชัน

รูปกราฟแสดงการเติบโตของฟังก์ชัน

        ตามประสิทธิภาพอัลกอริทึมจากมากที่สุด(ใช้เวลาน้อยที่สุด)ไปหาน้อยที่สุด

        C > logN > Log2N > √N > N > N log N > N2 > N3…Nk > 2n, cn > N!