สัญกรณ์โอใหญ่
จากวิกิพีเดีย สารานุกรมเสรี
ในวิชาทฤษฎีความซับซ้อนและคณิตศาสตร์ สัญกรณ์โอใหญ่ (อังกฤษ: Big O notation) เป็นสัญกรณ์คณิตศาสตร์ที่ใช้บรรยายพฤติกรรมเชิงเส้นกำกับของฟังก์ชัน โดยระบุเป็นขนาด (magnitude) ของฟังก์ชันในพจน์ของฟังก์ชันอื่นที่โดยทั่วไปซับซ้อนน้อยกว่า อาทิฟังก์ชัน n2 + n และ n2 + 4 ล้วนมีอัตราการเติบโตเดียวกับ n2 เราจะกล่าวได้ว่า n2 + n และ n2 + 4 เป็นสมาชิกของเซตของฟังก์ชัน O(n2)
สัญกรณ์โอใหญ่ใช้ในการเขียนเพื่อประมาณพจน์ในคณิตศาสตร์ และประยุกต์ใช้ในวิทยาการคอมพิวเตอร์เพื่อใช้อธิบายความเร็วในการทำงานโปรแกรม สำหรับข้อมูลจำนวนมาก เพื่ออธิบายประสิทธิภาพของขั้นตอนวิธี หรือ โครงสร้างข้อมูล นั้นๆ
เนื้อหา |
[แก้] ประวัติ
แนวคิดของสัญกรณ์โอใหญ่ถูกคิดโดยนักทฤษฎีจำนวนที่ชื่อพอล แบชมาน (Paul Bachman) จากงานตีพิมพ์ของเขาที่ชื่อว่า Analytische Zahlentheorie (ทฤษฎีจำนวนวิเคราะห์) ในปี 1894 โดยครั้งนั้นยังไม่ได้ใช้ตัวสัญกรณ์โอใหญ่ สำหรับตัวสัญกรณ์โอใหญ่เองได้รับการใช้อย่างแพร่หลายโดยนักทฤษฎีจำนวนชาวเยอรมัน ที่มีชื่อว่า เอ็ดมึนด์ ลานเดา (Edmund Landau) ชื่อของเขาบางครั้งได้รับการยกย่องให้เป็นชื่อของสัญกรณ์โอใหญ่ว่าเป็น สัญกรณ์ของลานเดา (Landau notation) หรือ สัญกรณ์แบชมาน-ลานเดา (Bachmann-Landau notation) สำหรับตัวสัญกรณ์ที่เขียนเป็นรูปโอใหญ่นั้นได้แนวคิดมาจากคำว่า "order of" ซึ่งเดิมทีนั้นเขียนโดยใช้เป็นโอไมครอนใหญ่
[แก้] นิยาม
นิยามของสัญกรณ์โอใหญ่มีสองรูปแบบแต่มีความหมายในทางเดียวกันว่า อัตราการเติบโตของฟังก์ชันใดๆ มีค่าเป็นสัญกรณ์โอใหญ่ของอีกฟังก์ชันหนึ่งแล้ว แสดงว่าอัตราการเติบโตของฟังก์ชันใดๆนั้นจะโตน้อยกว่าหรือเท่ากับอัตราการเติบโตของฟังก์ชันดังกล่าว
เหตุที่มีนิยามแตกต่างกันเพื่อรองรับฟังก์ชันที่มีลักษณะโดเมนที่แตกต่างกัน แต่ส่วนมากถ้าฟังก์ชันใดใช้นิยามได้มากกว่าสองอันแล้ว มักจะได้คำตอบตรงกัน และทั้งสองนิยามสามารถขยายไปถึงสัญกรณ์โอใหญ่ของหลายตัวแปรได้
[แก้] นิยามแบบที่หนึ่ง
ให้ f (n) และ g (n) เป็นฟังก์ชันใดๆ
ก็ต่อเมื่อ- มีจำนวนจริง c และ n0 ค่าหนึ่งที่ทำให้
ทุกๆ 
[แก้] ตัวอย่างจากนิยามนี้
ทุกๆ
(หาได้จากการแก้อสมการ) เพราะฉะนั้น
(c = 2,n0 = 1)
ทุกๆ
(หาได้จากการแก้อสมการ) เพราะฉะนั้น
(c = 2,n0 = 2)
[แก้] การขยายนิยามไปหลายตัวแปร
ให้
และ
เป็นฟังก์ชันหลายตัวแปรใดๆ
ก็ต่อเมื่อ- มีจำนวนจริง c และ n0 ค่าหนึ่งที่ทำให้
ทุกๆ 
[แก้] นิยามแบบที่สอง
ให้ f (x) และ g (x) เป็นฟังก์ชันใดๆ
ก็ต่อเมื่อ
ในนิยามนี้สามารถขยายไปถึงสัญกรณ์โอใหญ่กณิกนันต์ กล่าวคือพิจารณาอัตรากการเติบโตของฟังกชันรอบๆจุด a ใดๆว่า
ขณะ x เข้าใกล้ a ก็ต่อเมื่อ
[แก้] ตัวอย่างจากนิยามนี้
เพราะฉะนั้น 
เพราะฉะนั้น 
[แก้] การขยายนิยามไปหลายตัวแปร
ให้
และ
เป็นฟังก์ชันหลายตัวแปรใดๆ
ก็ต่อเมื่อ
เช่นเดียวกันขยายไปถึงสัญกรณ์โอใหญ่กณิกนันต์ กล่าวคือพิจารณาอัตราการเติบโตของฟังก์ชันรอบๆพิกัด
ใดๆว่า
ก็ต่อเมื่อ
[แก้] การใช้งาน
สัญกรณ์โอใหญ่มีการใช้ในสองกรณีด้วยกัน ได้แก่ กรณีเส้นกำกับอนันต์ และ กรณีเส้นกำกับกณิกนันต์ ความแตกต่างระหว่างสองกรณีนี้เป็นความแตกต่างในขั้นการประยุกต์ใช้ มิใช่ในขั้นหลักการ อย่างไรก็ตาม นิยามเชิงรูปนัยของ "โอใหญ่" นั้นเหมือนกันในทั้งสองกรณี มีเพียงลิมิตสำหรับอาร์กิวเมนต์ของฟังก์ชันเท่านั้นที่แตกต่างกัน
[แก้] กรณีเส้นกำกับอนันต์
สัญกรณ์โอใหญ่มีประโยชน์ในการใช้วิเคราะห์ขั้นตอนวิธี เพื่อหาประสิทธิภาพของขั้นตอนวิธี ตัวอย่างเช่น สมมติให้เวลา (หรือจำนวนขั้นตอน) ที่ใช้ในการแก้ปัญหาขนาด n มีฟังก์ชันเป็น T(n) = 4n2 − 2n + 2
เมื่อ n มีค่ามากขึ้น พจน์ n2 จะใหญ่ขึ้นครอบงำพจน์อื่น ๆ จนกระทั่งเราสามารถละเลยพจน์อื่น ๆ ได้ ยิ่งไปกว่านั้น สัมประสิทธิ์ของแต่ละพจน์จะขึ้นกับรายละเอียดปลีกย่อยของการนำขั้นตอนวิธีไปปฏิบัติ ตลอดจนฮาร์ดแวร์ที่ใช้ในการดำเนินการ ฉะนั้นจึงสามารถละเลยได้เช่นกัน สัญกรณ์โอใหญ่จะเก็บเฉพาะส่วนที่เหลือจากที่ละเลยได้ข้างต้น จึงเขียนได้ว่า
และกล่าวได้ว่า ขั้นตอนวิธีดังตัวอย่างนี้มีความซับซ้อนเชิงเวลาเป็นอันดับของ n2
[แก้] กรณีเส้นกำกับกณิกนันต์
สัญกรณ์โอใหญ่ยังใช้เพื่อแสดงพจน์ของค่าคลาดเคลื่อนโดยประมาณในฟังก์ชันทางคณิตศาสตร์ ตัวอย่างเช่น
หมายความว่า เมื่อ x มีค่าเข้าใกล้ศูนย์ ผลต่างของฟังก์ชันex กับ 1 + x + x2 / 2 (หรืออาจกล่าวอีกนัยหนึ่งว่าเป็นความคลาดเคลื่อนของสองฟังก์ชันนี้) จะมีอยู่ในสับเซตของO(x3)นั่นเอง หรือเขียนเป็นสัญลักษณ์ว่า
[แก้] คุณสมบัติ
[แก้] การบวก
- บทเสริม

- บทเสริม
[แก้] การคูณ
[แก้] การคูณด้วยค่าคงที่
ให้ k เป็นค่าคงที่ใดๆ ที่เป็นบวก
[แก้] การซ้อนสัญกรณ์โอใหญ่
ให้ h (n) เป็นอีกฟังก์ชันหนึ่ง
[แก้] สัญกรณ์โอใหญ่มาตรฐานน้อยสุด
ในบางครั้งสัญกรณ์โอใหญ่อาจมีการครอบคลุมมากเกินไป เช่น
เป็นต้น จึงทำให้สำหรับฟังก์ชันใดๆ อาจอยู่ในเซตของสัญกรณ์โอใหญ่หลายค่า จึงมีการกำหนดรูปแบบฟังก์ชันอย่างง่าย ให้ตอบในรูปสัญกรณ์โอใหญ่มาตรฐานน้อยสุด กล่าวคือตอบในรูปแบบมาตรฐานที่เล็กที่สุด เรามักจะอนุโลมให้ใช้จากสัญลักษณ์เท่ากับ ( = ) แทนสัญลักษณ์สมาชิก (
) เมื่อใช้กับรูปสัญกรณ์โอใหญ่มาตรฐานน้อยสุดนี้ เช่น n2 + 4 = O(n2)
ในทางวิทยาการคอมพิวเตอร์ การทำงานที่มีสัญกรณ์โอใหญ่มาตรฐานน้อยสุดมีขนาดยิ่งเล็กเท่าใด แสดงว่าทำงานได้ยิ่งเร็วเท่านั้น
สัญกรณ์โอใหญ่มาตรฐานเรียงจากขนาดเล็กไปใหญ่ (ขนาดเล็กหมายถึงจะเป็นซับเซตของขนาดที่ใหญ่กว่า) ให้ m เป็นค่าคงที่ใดๆ ที่มากกว่าศูนย์ และ n เป็นโดเมนของฟังก์ชัน
| สัญกรณ์โอใหญ่มาตรฐาน | ชื่อฟังก์ชัน | หมายเหตุ |
|---|---|---|
| O(1) | ค่าคงที่ | ไม่ใช้ค่าคงที่อื่นในการแสดงสัญกรณ์ เช่นไม่มีการใช้ O (2) |
| O(logn) | ลอการิทึม | ลอการิทึมทุกฐานอยู่ในระดับเดียวกัน เพราะเปลี่ยนฐานได้โดยคูณค่าคงที่ |
| O(kn) 0<k<1 | เอกซ์โพเนนเชียลฐานเศษส่วนแท้ | ยิ่งค่าฐานมากยิ่งใหญ่ |
| O((logn)m) | โพลีลอการิทึม | ยิ่งเลขชี้กำลังมากระดับยิ่งใหญ่ |
| O(nk),0 < k < 1 | ยกกำลังที่เป็นเศษส่วนแท้ (ติดราก) | ยิ่งเลขชี้กำลังมากระดับยิ่งใหญ่ |
| O(n) | เชิงเส้น | จริงๆแล้วเป็นพหุนามรูปแบบหนึ่ง แยกมาเรียกเพราะใช้บ่อย |
| O(nk),k > 1 | พหุนาม | ยิ่งเลขชี้กำลังมากระดับยิ่งใหญ่ |
| O(kn) k>1 | เอกซ์โพเนนเชียล | ยิ่งค่าฐานมากยิ่งใหญ่ |
| O(n!) | แฟกทอเรียล | อาจรวมถึงการเรียงลำดับสับเปลี่ยน (permutation) |
| O(nn) | n ยกกำลัง n | มีบางครั้งคนใช้ O (nn) แทน O (n!) แต่ที่จริง O (nn) ใหญ่กว่า O (n!) เล็กน้อย |
บางครั้งเราจำเป็นต้องใช้การผสมโดยการคูณเช่น O(nlogn) เกิดจากการคูณระหว่างเชิงเส้นและลอการิทึมย่อมทำได้











