ในวิชาทฤษฎีความซับซ้อน วิทยาการคอมพิวเตอร์ และคณิตศาสตร์ สัญกรณ์โอใหญ่ (Big O notation) เป็นสัญกรณ์คณิตศาสตร์ที่ใช้บรรยายพฤติกรรมเชิงเส้นกำกับของฟังก์ชัน หากกล่าวให้แจ้งชัด สัญกรณ์โอใหญ่นั้นใช้เพื่อบรรยายขอบเขตบนเชิงเส้นกำกับ โดยระบุเป็นขนาด (magnitude) ของฟังก์ชันในพจน์ของฟังก์ชันอื่นที่โดยทั่วไปซับซ้อนน้อยกว่า

การใช้

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

กรณีเส้นกำกับอนันต์

สัญกรณ์โอใหญ่มีประโยชน์ในการใช้วิเคราะห์ขั้นตอนวิธี เพื่อหาประสิทธิภาพของขั้นตอนวิธี ตัวอย่างเช่น สมมติให้เวลา (หรือจำนวนขั้นตอน) ที่ใช้ในการแก้ปัญหาขนาด n มีฟังก์ชันเป็น T(n) = 4n² - 2n + 2.

เมื่อ n มีค่ามากขึ้น พจน์ n² จะใหญ่ขึ้นครอบงำพจน์อื่น ๆ จนกระทั่งเราสามารถละเลยพจน์อื่น ๆ ได้ ยิ่งไปกว่านั้น สัมประสิทธิ์ของแต่ละพจน์จะขึ้นกับรายละเอียดปลีกย่อยของการนำขั้นตอนวิธีไปปฏิบัติ ตลอดจนฮาร์ดแวร์ที่ใช้ในการดำเนินการ ฉะนั้นจึงสามารถละเลยได้เช่นกัน สัญกรณ์โอใหญ่จะเก็บเฉพาะส่วนที่เหลือจากที่ละเลยได้ข้างต้น จึงเขียนได้ว่า

$T(n)\backslash in\; O(n^2)$

และกล่าวได้ว่า ขั้นตอนวิธีดังตัวอย่างนี้มีความซับซ้อนเชิงเวลาเป็นอันดับของ n²

กรณีเส้นกำกับกณิกนันต์

สัญกรณ์โอใหญ่ยังใช้เพื่อแสดงพจน์ของค่าคลาดเคลื่อนโดยประมาณในฟังก์ชันทางคณิตศาสตร์ ตัวอย่างเช่น

$e^x=1+x+x^2/2+\backslash hbox\{O\}(x^3)\backslash qquad\backslash hbox\{as\}\backslash \; x\backslash to\; 0$

แสดงข้อเท็จจริงว่า ค่าคลาดเคลื่อนของฟังก์ชันนี้มีค่าสัมบูรณ์น้อยกว่าผลคูณระหว่างค่าคงตัวกับ x³ เมื่อ x มีค่าเข้าใกล้ศูนย์

คณิตวิเคราะห์

Big O notation | ランダウの記号 | Notacja dużego O | 大O符号