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

ในวิชาทฤษฎีความซับซ้อนและคณิตศาสตร์ สัญกรณ์โอใหญ่  เป็นสัญกรณ์คณิตศาสตร์ที่ใช้บรรยายพฤติกรรมเชิงเส้นกำกับของฟังก์ชัน โดยระบุเป็นขนาด (magnitude) ของฟังก์ชันในพจน์ของฟังก์ชันอื่นที่โดยทั่วไปซับซ้อนน้อยกว่า สัญกรณ์โอใหญ่เป็นหนึ่งในสัญกรณ์เชิงเส้นกำกับ หรืออาจเรียกว่า สัญกรณ์ของลันเดา หรือ สัญกรณ์ของบัคแมนน์-ลันเดา (ตั้งชื่อตามเอ็ดมุนด์ ลานเดาและเพาล์ บาคมันน์) สัญกรณ์โอใหญ่ใช้ในการเขียนเพื่อประมาณพจน์ในคณิตศาสตร์ ประยุกต์ใช้ในวิทยาการคอมพิวเตอร์เพื่อใช้อธิบายความเร็วประมาณในการทำงานของโปรแกรมในกรณีต้องประมวลผลข้อมูลจำนวนมาก และใช้เพื่ออธิบายประสิทธิภาพของขั้นตอนวิธีหรือโครงสร้างข้อมูลนั้น ๆ
สัญกรณ์โอใหญ่ระบุลักษณะของฟังก์ชันตามอัตราการเติบโต ถึงแม้ฟังก์ชันจะต่างกัน แต่ถ้ามีอัตราการเติบโตเท่ากันก็จะมีสัญกรณ์โอใหญ่เท่ากัน สำหรับสัญกรณ์โอใหญ่แล้ว จะพิจารณาเฉพาะขอบเขตบนของอัตราการเติบโตของฟังก์ชัน อาทิฟังก์ชัน <math>n^2+n</math> และ <math>n+4</math> ล้วนมีอัตราการเติบโต"น้อยกว่า"หรือ"เท่ากับ" <math>n^2</math> นั่นคืออัตราการเติบโตของฟังก์ชัน <math>n^2</math> เป็นขอบเขตบนของ <math>n^2+n</math> และ <math>n+4</math> จึงอาจกล่าวได้ว่า <math>n^2+n</math> และ <math>n+4</math> เป็นสมาชิกของเซตของฟังก์ชัน <math>O (n^2) </math> ในขณะที่สัญกรณ์เชิงเส้นกำกับอื่น พิจารณาขอบเขตอื่น ๆ เช่นสัญกรณ์โอเมกาใหญ่พิจารณาขอบเขตล่างของอัตราการเติบโตของฟังก์ชันแทน
ประวัติ.
แนวคิดของสัญกรณ์โอใหญ่ถูกคิดโดยนักทฤษฎีจำนวนที่ชื่อเพาล์ บาคมันน์ (Paul Bachmann) จากงานตีพิมพ์ของเขาที่ชื่อว่า "Analytische Zahlentheorie" (ทฤษฎีจำนวนวิเคราะห์) ในปี 1894 โดยครั้งนั้นยังไม่ได้ใช้ตัวสัญกรณ์โอใหญ่ สำหรับตัวสัญกรณ์โอใหญ่เองได้รับการใช้อย่างแพร่หลายโดยนักทฤษฎีจำนวนชาวเยอรมัน ที่มีชื่อว่า เอ็ดมุนด์ ลานเดา (Edmund Landau) ชื่อของเขาบางครั้งได้รับการยกย่องให้เป็นชื่อของสัญกรณ์โอใหญ่ว่าเป็น สัญกรณ์ของลานเดา (Landau notation) หรือ สัญกรณ์แบชมาน-ลานเดา (Bachmann-Landau notation) สำหรับตัวสัญกรณ์ที่เขียนเป็นรูปโอใหญ่นั้นได้แนวคิดมาจากคำว่า "order of" ซึ่งเดิมทีนั้นเขียนโดยใช้เป็นโอไมครอนใหญ่
นิยาม.
อัตราการเติบโตของฟังก์ชันใด ๆ มีค่าเป็นสัญกรณ์โอใหญ่ของอีกฟังก์ชันหนึ่งแล้ว แสดงว่าอัตราการเติบโตของฟังก์ชันใด ๆ นั้นจะ "โตน้อยกว่าหรือเท่ากับ" อัตราการเติบโตของฟังก์ชันดังกล่าว ดังนั้นจึงอาจนิยามได้ว่า
ให้ <math>f (n)</math> และ <math>g (n)</math> เป็นฟังก์ชันบนจำนวนจริงใด ๆ แล้ว จะกล่าวว่า
<math>f (n) \in O (g (n)) </math> เมื่อ <math>n\to\infty</math>
ก็ต่อเมื่อมีจำนวนจริง <math>c</math> และ <math>n_0</math> ค่าหนึ่งที่ทำให้ <math> |f (n)|\le c|g (n)| </math> ทุก ๆ <math> n \ge n_0 </math>
อย่างไรก็ตาม นิยามนี้จำกัดเฉพาะกรณี <math>n\to\infty</math> เท่านั้น ซึ่งไม่เพียงพอต่อการอธิบายในกรณีที่ <math>n\to a</math> ดังนั้นจึงอาจใช้นิยามในอีกรูปแบบ ในการขยายไปถึงสัญกรณ์โอใหญ่กณิกนันต์ ซึ่งเป็นพิจารณาอัตราการเติบโตของฟังกชันรอบ ๆ จุด a ใด ๆ
ให้ <math>f (x)</math> และ <math>g (x)</math> เป็นฟังก์ชันใด ๆ จะกล่าวว่า
<math>f (x) \in O (g (x)) </math> ขณะ x เข้าใกล้ a
ก็ต่อเมื่อ <math>\lim_{x\to a} \left|\frac{f (x) }{g (x) }\right| \in [0,\infty)</math>
การขยายนิยามไปหลายตัวแปร.
นิยามทั้งสองรูปแบบสามารถขยายไปหลายตัวแปรได้
ให้ <math>f (a_0,a_1,\ldots,a_n) </math> และ <math>g (a_0,a_1,\ldots,a_n) </math> เป็นฟังก์ชันหลายตัวแปรใด ๆ จะกล่าวได้ว่า
<math>f (a_0,a_1,\ldots,a_n) \in O (a_0,a_1,\ldots,a_n) </math>
ก็ต่อเมื่อมีจำนวนจริง <math>c</math> และ <math>n_0</math> ค่าหนึ่งที่ทำให้ <math> |f (a_0,a_1,\ldots,a_n)|\le c |g (a_0,a_1,\ldots,a_n)| </math> ทุก ๆ <math> a_0,a_1,\ldots,a_n \ge n_0 </math>
หรือในอีกนิยามที่พิจารณาอัตราการเติบโตของฟังก์ชันรอบ ๆ พิกัด <math> (k_0,k_1,\ldots,k_n) </math> ใด ๆ ว่า
<math>f (a_0,a_1,\ldots,a_n) \in O (g (a_0,a_1,\ldots,a_n)) </math>
ก็ต่อเมื่อ <math>\lim_{a_0,a_1,\ldots,a_n \to k_0,k_1,\ldots,k_n} \left|\frac{f (a_0,a_1,\ldots,a_n) }{g (a_0,a_1,\ldots,a_n) }\right| \in [0,\infty).</math>
ตัวอย่าง.
หรือ
การใช้งาน.
สัญกรณ์โอใหญ่มีการใช้ในสองกรณีด้วยกัน ได้แก่ กรณีเส้นกำกับอนันต์ และ กรณีเส้นกำกับกณิกนันต์ ความแตกต่างระหว่างสองกรณีนี้เป็นความแตกต่างในขั้นการประยุกต์ใช้ มิใช่ในขั้นหลักการ อย่างไรก็ตาม นิยามเชิงรูปนัยของ "โอใหญ่" นั้นเหมือนกันในทั้งสองกรณี มีเพียงลิมิตสำหรับอาร์กิวเมนต์ของฟังก์ชันเท่านั้นที่แตกต่างกัน
กรณีเส้นกำกับอนันต์.
สัญกรณ์โอใหญ่มีประโยชน์ในการใช้วิเคราะห์ขั้นตอนวิธี เพื่อหาประสิทธิภาพของขั้นตอนวิธี ตัวอย่างเช่น สมมติให้เวลา (หรือจำนวนขั้นตอน) ที่ใช้ในการแก้ปัญหาขนาด "n" มีฟังก์ชันเป็น <math>T (n) = 4n^2 - 2n + 2 </math>
เมื่อ "n" มีค่ามากขึ้น พจน์ "n"2 จะใหญ่ขึ้นครอบงำพจน์อื่น ๆ จนกระทั่งเราสามารถละเลยพจน์อื่น ๆ ได้ ยิ่งไปกว่านั้น สัมประสิทธิ์ของแต่ละพจน์จะขึ้นกับรายละเอียดปลีกย่อยของการนำขั้นตอนวิธีไปปฏิบัติ ตลอดจนฮาร์ดแวร์ที่ใช้ในการดำเนินการ ฉะนั้นจึงสามารถละเลยได้เช่นกัน สัญกรณ์โอใหญ่จะเก็บเฉพาะส่วนที่เหลือจากที่ละเลยได้ข้างต้น จึงเขียนได้ว่า
<math>T (n) \in O (n^2) </math>
และกล่าวได้ว่า ขั้นตอนวิธีดังตัวอย่างนี้มีความซับซ้อนเชิงเวลาเป็น"อันดับของ n2"
กรณีเส้นกำกับกณิกนันต์.
สัญกรณ์โอใหญ่ยังใช้เพื่อแสดงพจน์ของค่าคลาดเคลื่อนโดยประมาณในฟังก์ชันทางคณิตศาสตร์ ตัวอย่างเช่น
<math>e^x=1+x+\frac{x^2}{2}+\hbox{O} (x^3) \qquad\hbox{as}\ x\to 0</math>
หมายความว่า เมื่อ "x" มีค่าเข้าใกล้ศูนย์ ผลต่างของฟังก์ชัน <math> e^x</math> กับ <math>1+x+x^2/2</math> (หรืออาจกล่าวอีกนัยหนึ่งว่าเป็นความคลาดเคลื่อนของสองฟังก์ชันนี้) จะมีอยู่ในสับเซตของ <math>O (x^3) </math> นั่นเอง หรือเขียนเป็นสัญลักษณ์ว่า
<math>\left|e^x-\left (1+x+\frac{x^2}{2}\right) \right| \in \hbox{O} (x^3) \qquad\hbox{as}\ x\to 0</math>
คุณสมบัติ.
การคูณด้วยค่าคงที่.
ให้ k เป็นค่าคงที่ใด ๆ ที่เป็นบวก
<math>O (k \cdot g) = O (g) </math>
<math>f\in O (g) \Rightarrow k\cdot f \in O (g) </math>
<math>f (n) \in O (g (n)) \implies O (f (n)) \subset O (g (n)) </math>
การซ้อนสัญกรณ์โอใหญ่.
ให้ h (n) เป็นอีกฟังก์ชันหนึ่ง
<math>O (f (n)) \in O (g (n)) \implies O (f (h (n))) \subset O (g (h (n))) </math>
สัญกรณ์โอใหญ่มาตรฐานน้อยสุด.
ในบางครั้งสัญกรณ์โอใหญ่อาจมีการครอบคลุมมากเกินไป เช่น <math> O (n^2) \subset O (n^3) </math> เป็นต้น จึงทำให้สำหรับฟังก์ชันใด ๆ อาจอยู่ในเซตของสัญกรณ์โอใหญ่หลายค่า จึงมีการกำหนดรูปแบบฟังก์ชันอย่างง่าย ให้ตอบในรูปสัญกรณ์โอใหญ่มาตรฐานน้อยสุด กล่าวคือตอบในรูปแบบมาตรฐานที่เล็กที่สุด เรามักจะอนุโลมให้ใช้จากสัญลักษณ์เท่ากับ (<math>=</math>) แทนสัญลักษณ์สมาชิก (<math>\in</math>) เมื่อใช้กับรูปสัญกรณ์โอใหญ่มาตรฐานน้อยสุดนี้ เช่น <math>n^2+4 = O (n^2) </math>
ในทางวิทยาการคอมพิวเตอร์ การทำงานที่มีสัญกรณ์โอใหญ่มาตรฐานน้อยสุดมีขนาดยิ่งเล็กเท่าใด แสดงว่าทำงานได้ยิ่งเร็วเท่านั้น
สัญกรณ์โอใหญ่มาตรฐานเรียงจากขนาดเล็กไปใหญ่ (ขนาดเล็กหมายถึงจะเป็นซับเซตของขนาดที่ใหญ่กว่า)
ให้ m เป็นค่าคงที่ใด ๆ ที่มากกว่าศูนย์ และ n เป็นโดเมนของฟังก์ชัน 
บางครั้งเราจำเป็นต้องใช้การผสมโดยการคูณเช่น <math>O (n log n) </math> เกิดจากการคูณระหว่างเชิงเส้นและลอการิทึมย่อมทำได้