สัญกรณ์โอใหญ่มาตรฐานน้อยสุด ของ สัญกรณ์โอใหญ่

ในบางครั้งสัญกรณ์โอใหญ่อาจมีการครอบคลุมมากเกินไป เช่น O ( n 2 ) ⊂ O ( n 3 ) {\displaystyle O(n^{2})\subset O(n^{3})} เป็นต้น จึงทำให้สำหรับฟังก์ชันใดๆ อาจอยู่ในเซตของสัญกรณ์โอใหญ่หลายค่า จึงมีการกำหนดรูปแบบฟังก์ชันอย่างง่าย ให้ตอบในรูปสัญกรณ์โอใหญ่มาตรฐานน้อยสุด กล่าวคือตอบในรูปแบบมาตรฐานที่เล็กที่สุด เรามักจะอนุโลมให้ใช้จากสัญลักษณ์เท่ากับ ( = {\displaystyle =} ) แทนสัญลักษณ์สมาชิก ( ∈ {\displaystyle \in } ) เมื่อใช้กับรูปสัญกรณ์โอใหญ่มาตรฐานน้อยสุดนี้ เช่น n 2 + 4 = O ( n 2 ) {\displaystyle n^{2}+4=O(n^{2})}

ในทางวิทยาการคอมพิวเตอร์ การทำงานที่มีสัญกรณ์โอใหญ่มาตรฐานน้อยสุดมีขนาดยิ่งเล็กเท่าใด แสดงว่าทำงานได้ยิ่งเร็วเท่านั้น

สัญกรณ์โอใหญ่มาตรฐานเรียงจากขนาดเล็กไปใหญ่ (ขนาดเล็กหมายถึงจะเป็นซับเซตของขนาดที่ใหญ่กว่า)ให้ m เป็นค่าคงที่ใดๆ ที่มากกว่าศูนย์ และ n เป็นโดเมนของฟังก์ชัน


สัญกรณ์โอใหญ่มาตรฐาน	ชื่อฟังก์ชัน	หมายเหตุ
O ( 1 ) {\displaystyle O(1)}	ค่าคงที่	ไม่ใช้ค่าคงที่อื่นในการแสดงสัญกรณ์ เช่นไม่มีการใช้ O (2)
O ( log ⁡ n ) {\displaystyle O(\log n)}	ลอการิทึม	ลอการิทึมทุกฐานอยู่ในระดับเดียวกัน เพราะเปลี่ยนฐานได้โดยคูณค่าคงที่
O ( k n ) {\displaystyle O(k^{n})} 0<k<1	เอกซ์โพเนนเชียลฐานเศษส่วนแท้	ยิ่งค่าฐานมากยิ่งใหญ่
O ( ( log ⁡ n ) m ) {\displaystyle O((\log n)^{m})}	โพลีลอการิทึม	ยิ่งเลขชี้กำลังมากระดับยิ่งใหญ่
O ( n k ) , 0 < k < 1 {\displaystyle O(n^{k}),0<k<1}	ยกกำลังที่เป็นเศษส่วนแท้ (ติดราก)	ยิ่งเลขชี้กำลังมากระดับยิ่งใหญ่
O ( n ) {\displaystyle O(n)}	เชิงเส้น	จริงๆแล้วเป็นพหุนามรูปแบบหนึ่ง แยกมาเรียกเพราะใช้บ่อย
O ( n k ) , k > 1 {\displaystyle O(n^{k}),k>1}	พหุนาม	ยิ่งเลขชี้กำลังมากระดับยิ่งใหญ่
O ( k n ) {\displaystyle O(k^{n})} k>1	เอกซ์โพเนนเชียล	ยิ่งค่าฐานมากยิ่งใหญ่
O ( n ! ) {\displaystyle O(n!)}	แฟกทอเรียล	อาจรวมถึงการเรียงลำดับสับเปลี่ยน (permutation)
O ( n n ) {\displaystyle O(n^{n})}	n ยกกำลัง n	มีบางครั้งคนใช้ O (nn) แทน O (n!) แต่ที่จริง O (nn) ใหญ่กว่า O (n!) เล็กน้อย

บางครั้งเราจำเป็นต้องใช้การผสมโดยการคูณเช่น O ( n l o g n ) {\displaystyle O(nlogn)} เกิดจากการคูณระหว่างเชิงเส้นและลอการิทึมย่อมทำได้

ใกล้เคียง