หลักๆจะมี
Big-O (Big O(n))
Big-Theta (Big Θ(n))
Big-Omega (Big Ω(n))
1) log n
2) n
3) n log n
4) n^2
5) n^3
6) x^n
7) n!
n คือจำนวน Inputและผลลัพธ์ของคลาสคือ จำนวนครั้งของ 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 เป็นเส้นบนและ Ω เป็นเส้นล่าง ดังรูปข้างล่าง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น