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

จากวิกิพีเดีย สารานุกรมเสรี

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

[แก้] การใช้งาน

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

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

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

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

T(n)\in O(n^2)

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

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

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

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

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


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