สัญกรณ์โอใหญ่
สัญกรณ์โอใหญ่

สัญกรณ์โอใหญ่

ในวิชาทฤษฎีความซับซ้อนและคณิตศาสตร์ สัญกรณ์โอใหญ่ (อังกฤษ: Big O notation) เป็นสัญกรณ์คณิตศาสตร์ที่ใช้บรรยายพฤติกรรมเชิงเส้นกำกับของฟังก์ชัน โดยระบุเป็นขนาด (magnitude) ของฟังก์ชันในพจน์ของฟังก์ชันอื่นที่โดยทั่วไปซับซ้อนน้อยกว่า สัญกรณ์โอใหญ่เป็นหนึ่งในสัญกรณ์เชิงเส้นกำกับ หรืออาจเรียกว่า สัญกรณ์ของลันเดา หรือ สัญกรณ์ของบัคแมนน์-ลันเดา (ตั้งชื่อตามเอ็ดมุนด์ ลานเดาและเพาล์ บาคมันน์) สัญกรณ์โอใหญ่ใช้ในการเขียนเพื่อประมาณพจน์ในคณิตศาสตร์ ประยุกต์ใช้ในวิทยาการคอมพิวเตอร์เพื่อใช้อธิบายความเร็วประมาณในการทำงานของโปรแกรมในกรณีต้องประมวลผลข้อมูลจำนวนมาก และใช้เพื่ออธิบายประสิทธิภาพของขั้นตอนวิธีหรือโครงสร้างข้อมูลนั้น ๆสัญกรณ์โอใหญ่ระบุลักษณะของฟังก์ชันตามอัตราการเติบโต ถึงแม้ฟังก์ชันจะต่างกัน แต่ถ้ามีอัตราการเติบโตเท่ากันก็จะมีสัญกรณ์โอใหญ่เท่ากัน สำหรับสัญกรณ์โอใหญ่แล้ว จะพิจารณาเฉพาะขอบเขตบนของอัตราการเติบโตของฟังก์ชัน อาทิฟังก์ชัน n 2 + n {\displaystyle n^{2}+n} และ n + 4 {\displaystyle n+4} ล้วนมีอัตราการเติบโตน้อยกว่าหรือเท่ากับ n 2 {\displaystyle n^{2}} นั่นคืออัตราการเติบโตของฟังก์ชัน n 2 {\displaystyle n^{2}} เป็นขอบเขตบนของ n 2 + n {\displaystyle n^{2}+n} และ n + 4 {\displaystyle n+4} จึงอาจกล่าวได้ว่า n 2 + n {\displaystyle n^{2}+n} และ n + 4 {\displaystyle n+4} เป็นสมาชิกของเซตของฟังก์ชัน O ( n 2 ) {\displaystyle O(n^{2})} ในขณะที่สัญกรณ์เชิงเส้นกำกับอื่น พิจารณาขอบเขตอื่น ๆ เช่นสัญกรณ์โอเมกาใหญ่พิจารณาขอบเขตล่างของอัตราการเติบโตของฟังก์ชันแทน

ใกล้เคียง

สัญกรณ์ระดับเสียงทางวิทยาศาสตร์ สัญกรณ์โอใหญ่ สัญกรณ์วิทยาศาสตร์ สัญกรณ์บรา-เค็ท สัญกรณ์ส่วนในหลายส่วน สัญกรณ์โพลิช สัญกรณ์ยกกำลัง สัญกรณ์ลูกศรของคนูธ สัญกรณ์คณิตศาสตร์ สัญกรณ์วัตถุจาวาสคริปต์