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

ในวิชาทฤษฎีความซับซ้อนและคณิตศาสตร์ สัญกรณ์โอใหญ่ (อังกฤษ: 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})} ในขณะที่สัญกรณ์เชิงเส้นกำกับอื่น พิจารณาขอบเขตอื่น ๆ เช่นสัญกรณ์โอเมกาใหญ่พิจารณาขอบเขตล่างของอัตราการเติบโตของฟังก์ชันแทน

แนวคิดของสัญกรณ์โอใหญ่ถูกคิดโดยนักทฤษฎีจำนวนที่ชื่อเพาล์ บาคมันน์ (Paul Bachmann) จากงานตีพิมพ์ของเขาที่ชื่อว่า Analytische Zahlentheorie (ทฤษฎีจำนวนวิเคราะห์) ในปี 1894 โดยครั้งนั้นยังไม่ได้ใช้ตัวสัญกรณ์โอใหญ่ สำหรับตัวสัญกรณ์โอใหญ่เองได้รับการใช้อย่างแพร่หลายโดยนักทฤษฎีจำนวนชาวเยอรมัน ที่มีชื่อว่า เอ็ดมุนด์ ลานเดา (Edmund Landau) ชื่อของเขาบางครั้งได้รับการยกย่องให้เป็นชื่อของสัญกรณ์โอใหญ่ว่าเป็น สัญกรณ์ของลานเดา (Landau notation) หรือ สัญกรณ์แบชมาน-ลานเดา (Bachmann-Landau notation) สำหรับตัวสัญกรณ์ที่เขียนเป็นรูปโอใหญ่นั้นได้แนวคิดมาจากคำว่า "order of" ซึ่งเดิมทีนั้นเขียนโดยใช้เป็นโอไมครอนใหญ่

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

อย่างไรก็ตาม นิยามนี้จำกัดเฉพาะกรณี n → ∞ {\displaystyle n\to \infty } เท่านั้น ซึ่งไม่เพียงพออธิบายในกรณีที่ n → a {\displaystyle n\to a} ดังนั้นจึงอาจใช้นิยามในอีกรูปแบบ ในการขยายไปถึงสัญกรณ์โอใหญ่กณิกนันต์ ซึ่งเป็นพิจารณาอัตราการเติบโตของฟังกชันรอบ ๆ จุด a ใด ๆ

หรือในอีกนิยามที่พิจารณาอัตราการเติบโตของฟังก์ชันรอบ ๆ พิกัด ( k 0 , k 1 , … , k n ) {\displaystyle (k_{0},k_{1},\ldots ,k_{n})} ใด ๆ ว่า

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

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

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

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

หมายความว่า เมื่อ x มีค่าเข้าใกล้ศูนย์ ผลต่างของฟังก์ชัน e x {\displaystyle e^{x}} กับ 1 + x + x 2 / 2 {\displaystyle 1+x+x^{2}/2} (หรืออาจกล่าวอีกนัยหนึ่งว่าเป็นความคลาดเคลื่อนของสองฟังก์ชันนี้) จะมีอยู่ในสับเซตของ O ( x 3 ) {\displaystyle O(x^{3})} นั่นเอง หรือเขียนเป็นสัญลักษณ์ว่า

ในบางครั้งสัญกรณ์โอใหญ่อาจมีการครอบคลุมมากเกินไป เช่น 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 ( n l o g n ) {\displaystyle O(nlogn)} เกิดจากการคูณระหว่างเชิงเส้นและลอการิทึมย่อมทำได้