หลักๆจะมี Big-O, Big-Theta, Big-Omega
ซึ่งจะแบ่งได้เป็น 7 คลาสหลักๆคือ
1) log n
2) n
3) n log n
4) n^2
5) n^3
6) x^n
7) n!
(คลาสคร่าวๆผิดถูกอย่างไรขออภัยไว้ด้วยครับ)
โดยที่ n คือจำนวน Input
และผลลัพธ์ของคลาสคือ จำนวนครั้งของ Basic Operation หรือจำนวนพื้นที่หน่วยความจำที่ถูกใช้
โดยที่ Big-O สัญลักษณ์คือ O เป็นขอบบนของจำนวนครั้งของ basic operation
เช่น O(n) หมายถึง Algorithm ของคุณใช้เวลารันหรือใช้พื้นที่หน่วยความจำไม่เกิน n
ส่วน Big-Theta สัญลักษณ์คือ Θ เป็นจำนวนครั้งของ basic operation
เช่น Θ(n^2) หมายถึง Algorithm ของคุณใช้เวลารันหรือใช้พื้นที่หน่วยความจำเท่ากับ n^2
และ Big-Omega สัญลักษณ์คือ Ω เป็นขอบล่างของจำนวนครั้งของ basic operation
เช่น Ω(n!) หมายถึง Algorithm ของคุณใช้เวลารันหรือใช้พื้นที่หน่วยความจำไม่น้อยกว่า n!
แถมอีกนิด Little-o สัญลักษณ์คือ o จะคล้ายๆกับ Big-O เรียกว่าเหมือนเลยก็ได้แต่ชัดเจนกว่าเพราะตัดเท่ากับออกไป
เช่น o(n^2) หมายถึง Algorithm ของคุณใช้เวลารันหรือใช้พื้นที่หน่วยความจำน้อยกว่า n^2
อีกหน่อยๆ Little-Omega สัญลักษณ์คือ ω ชัดเจนกว่า Big-Omega ในลักษณะคล้ายๆกับ Big-O และ Little-o โดยตัดเท่ากับออกไป
เช่น ω(n) หมายถึง Algorithm ของคุณใช้เวลารันหรือใช้พื้นที่หน่วยความจำมากกว่า n
ความสัมพันธ์ของ O Θ และ Ω จะเป็นประมาณว่า Θ เป็นเส้นกลาง O เป็นเส้นบนและ Ω เป็นเส้นล่าง ดังรูปข้างล่าง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น