บทความนี้ไม่มีจาก |
ในวิชาทฤษฎีความซับซ้อนและคณิตศาสตร์ สัญกรณ์โอใหญ่ (อังกฤษ: Big O notation) เป็นสัญกรณ์คณิตศาสตร์ที่ใช้บรรยายของฟังก์ชัน โดยระบุเป็น (magnitude) ของฟังก์ชันในของฟังก์ชันอื่นที่โดยทั่วไปซับซ้อนน้อยกว่า สัญกรณ์โอใหญ่เป็นหนึ่งในสัญกรณ์เชิงเส้นกำกับ หรืออาจเรียกว่า สัญกรณ์ของลันเดา หรือ สัญกรณ์ของบัคแมนน์-ลันเดา (ตั้งชื่อตามและ) สัญกรณ์โอใหญ่ใช้ในการเขียนเพื่อประมาณในคณิตศาสตร์ ประยุกต์ใช้ในวิทยาการคอมพิวเตอร์เพื่อใช้อธิบายความเร็วประมาณในการทำงานของโปรแกรมในกรณีต้องประมวลผลข้อมูลจำนวนมาก และใช้เพื่ออธิบายประสิทธิภาพของขั้นตอนวิธีหรือโครงสร้างข้อมูลนั้น ๆ
![image](https://www.wiki3.th-th.nina.az/image/aHR0cHM6Ly93d3cud2lraTMudGgtdGgubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODRMemc1TDBKcFp5MVBMVzV2ZEdGMGFXOXVMbkJ1Wnk4ME1EQndlQzFDYVdjdFR5MXViM1JoZEdsdmJpNXdibWM9LnBuZw==.png)
สัญกรณ์โอใหญ่ระบุลักษณะของฟังก์ชันตามอัตราการเติบโต ถึงแม้ฟังก์ชันจะต่างกัน แต่ถ้ามีอัตราการเติบโตเท่ากันก็จะมีสัญกรณ์โอใหญ่เท่ากัน สำหรับสัญกรณ์โอใหญ่แล้ว จะพิจารณาเฉพาะของอัตราการเติบโตของฟังก์ชัน อาทิฟังก์ชัน และ ล้วนมีอัตราการเติบโตน้อยกว่าหรือเท่ากับ นั่นคืออัตราการเติบโตของฟังก์ชัน เป็นขอบเขตบนของ และ จึงอาจกล่าวได้ว่า และ เป็นสมาชิกของเซตของฟังก์ชัน ในขณะที่สัญกรณ์เชิงเส้นกำกับอื่น พิจารณาขอบเขตอื่น ๆ เช่นสัญกรณ์โอเมกาใหญ่พิจารณาของอัตราการเติบโตของฟังก์ชันแทน
ประวัติ
แนวคิดของสัญกรณ์โอใหญ่ถูกคิดโดยนักทฤษฎีจำนวนที่ชื่อ (Paul Bachmann) จากงานตีพิมพ์ของเขาที่ชื่อว่า Analytische Zahlentheorie (ทฤษฎีจำนวนวิเคราะห์) ในปี 1894 โดยครั้งนั้นยังไม่ได้ใช้ตัวสัญกรณ์โอใหญ่ สำหรับตัวสัญกรณ์โอใหญ่เองได้รับการใช้อย่างแพร่หลายโดยนักทฤษฎีจำนวนชาวเยอรมัน ที่มีชื่อว่า (Edmund Landau) ชื่อของเขาบางครั้งได้รับการยกย่องให้เป็นชื่อของสัญกรณ์โอใหญ่ว่าเป็น สัญกรณ์ของลานเดา (Landau notation) หรือ สัญกรณ์แบชมาน-ลานเดา (Bachmann-Landau notation) สำหรับตัวสัญกรณ์ที่เขียนเป็นรูปโอใหญ่นั้นได้แนวคิดมาจากคำว่า "order of" ซึ่งเดิมทีนั้นเขียนโดยใช้เป็นโอไมครอนใหญ่
นิยาม
อัตราการเติบโตของฟังก์ชันใดๆ มีค่าเป็นสัญกรณ์โอใหญ่ของอีกฟังก์ชันหนึ่งแล้ว แสดงว่าอัตราการเติบโตของฟังก์ชันใดๆนั้นจะโตน้อยกว่าหรือเท่ากับอัตราการเติบโตของฟังก์ชันดังกล่าว ดังนั้นจึงอาจนิยามได้ว่า
- ให้
และ
เป็นฟังก์ชันบนจำนวนจริงใด ๆ แล้ว จะกล่าวว่า
เมื่อ
- ก็ต่อเมื่อมีจำนวนจริง
และ
ค่าหนึ่งที่ทำให้
ทุกๆ
อย่างไรก็ตาม นิยามนี้จำกัดเฉพาะกรณี เท่านั้น ซึ่งไม่เพียงพอต่อการอธิบายในกรณีที่
ดังนั้นจึงอาจใช้นิยามในอีกรูปแบบ ในการขยายไปถึงสัญกรณ์โอใหญ่กณิกนันต์ ซึ่งเป็นพิจารณาอัตราการเติบโตของฟังกชันรอบ ๆ จุด a ใด ๆ
- ให้
และ
เป็นฟังก์ชันใด ๆ จะกล่าวว่า
ขณะ x เข้าใกล้ a
- ก็ต่อเมื่อ
การขยายนิยามไปหลายตัวแปร
นิยามทั้งสองรูปแบบสามารถขยายไปหลายตัวแปรได้
- ให้
และ
เป็นใด ๆ จะกล่าวได้ว่า
- ก็ต่อเมื่อมีจำนวนจริง
และ
ค่าหนึ่งที่ทำให้
ทุก ๆ
หรือในอีกนิยามที่พิจารณาอัตราการเติบโตของฟังก์ชันรอบๆพิกัด ใดๆว่า
- ก็ต่อเมื่อ
ตัวอย่าง
หรือ
เพราะฉะนั้น
เพราะฉะนั้น
การใช้งาน
สัญกรณ์โอใหญ่มีการใช้ในสองกรณีด้วยกัน ได้แก่ กรณีเส้นกำกับอนันต์ และ กรณีเส้นกำกับกณิกนันต์ ความแตกต่างระหว่างสองกรณีนี้เป็นความแตกต่างในขั้นการประยุกต์ใช้ มิใช่ในขั้นหลักการ อย่างไรก็ตาม นิยามเชิงรูปนัยของ "โอใหญ่" นั้นเหมือนกันในทั้งสองกรณี มีเพียงลิมิตสำหรับของฟังก์ชันเท่านั้นที่แตกต่างกัน
กรณีเส้นกำกับอนันต์
สัญกรณ์โอใหญ่มีประโยชน์ในการใช้วิเคราะห์ขั้นตอนวิธี เพื่อหาประสิทธิภาพของขั้นตอนวิธี ตัวอย่างเช่น สมมติให้เวลา (หรือจำนวนขั้นตอน) ที่ใช้ในการแก้ปัญหาขนาด n มีฟังก์ชันเป็น
เมื่อ n มีค่ามากขึ้น พจน์ n2 จะใหญ่ขึ้นครอบงำพจน์อื่น ๆ จนกระทั่งเราสามารถละเลยพจน์อื่น ๆ ได้ ยิ่งไปกว่านั้น สัมประสิทธิ์ของแต่ละพจน์จะขึ้นกับรายละเอียดปลีกย่อยของการนำขั้นตอนวิธีไปปฏิบัติ ตลอดจนฮาร์ดแวร์ที่ใช้ในการดำเนินการ ฉะนั้นจึงสามารถละเลยได้เช่นกัน สัญกรณ์โอใหญ่จะเก็บเฉพาะส่วนที่เหลือจากที่ละเลยได้ข้างต้น จึงเขียนได้ว่า
และกล่าวได้ว่า ขั้นตอนวิธีดังตัวอย่างนี้มีความซับซ้อนเชิงเวลาเป็นอันดับของ n2
กรณีเส้นกำกับกณิกนันต์
สัญกรณ์โอใหญ่ยังใช้เพื่อแสดงพจน์ของค่าคลาดเคลื่อนโดยประมาณในฟังก์ชันทางคณิตศาสตร์ ตัวอย่างเช่น
หมายความว่า เมื่อ x มีค่าเข้าใกล้ศูนย์ ผลต่างของฟังก์ชัน กับ
(หรืออาจกล่าวอีกนัยหนึ่งว่าเป็นความคลาดเคลื่อนของสองฟังก์ชันนี้) จะมีอยู่ในสับเซตของ
นั่นเอง หรือเขียนเป็นสัญลักษณ์ว่า
คุณสมบัติ
การคูณ
การคูณด้วยค่าคงที่
ให้ k เป็นค่าคงที่ใดๆ ที่เป็นบวก
การซ้อนสัญกรณ์โอใหญ่
ให้ h (n) เป็นอีกฟังก์ชันหนึ่ง
สัญกรณ์โอใหญ่มาตรฐานน้อยสุด
ในบางครั้งสัญกรณ์โอใหญ่อาจมีการครอบคลุมมากเกินไป เช่น เป็นต้น จึงทำให้สำหรับฟังก์ชันใดๆ อาจอยู่ในเซตของสัญกรณ์โอใหญ่หลายค่า จึงมีการกำหนดรูปแบบฟังก์ชันอย่างง่าย ให้ตอบในรูปสัญกรณ์โอใหญ่มาตรฐานน้อยสุด กล่าวคือตอบในรูปแบบมาตรฐานที่เล็กที่สุด เรามักจะอนุโลมให้ใช้จากสัญลักษณ์เท่ากับ (
) แทนสัญลักษณ์สมาชิก (
) เมื่อใช้กับรูปสัญกรณ์โอใหญ่มาตรฐานน้อยสุดนี้ เช่น
ในทางวิทยาการคอมพิวเตอร์ การทำงานที่มีสัญกรณ์โอใหญ่มาตรฐานน้อยสุดมีขนาดยิ่งเล็กเท่าใด แสดงว่าทำงานได้ยิ่งเร็วเท่านั้น
สัญกรณ์โอใหญ่มาตรฐานเรียงจากขนาดเล็กไปใหญ่ (ขนาดเล็กหมายถึงจะเป็นซับเซตของขนาดที่ใหญ่กว่า) ให้ m เป็นค่าคงที่ใดๆ ที่มากกว่าศูนย์ และ n เป็นโดเมนของฟังก์ชัน
สัญกรณ์โอใหญ่มาตรฐาน | ชื่อฟังก์ชัน | หมายเหตุ |
---|---|---|
ค่าคงที่ | ไม่ใช้ค่าคงที่อื่นในการแสดงสัญกรณ์ เช่นไม่มีการใช้ O (2) | |
ลอการิทึม | ลอการิทึมทุกฐานอยู่ในระดับเดียวกัน เพราะเปลี่ยนฐานได้โดยคูณค่าคงที่ | |
เอกซ์โพเนนเชียลฐานเศษส่วนแท้ | ยิ่งค่าฐานมากยิ่งใหญ่ | |
โพลีลอการิทึม | ยิ่งเลขชี้กำลังมากระดับยิ่งใหญ่ | |
ยกกำลังที่เป็นเศษส่วนแท้ (ติดราก) | ยิ่งเลขชี้กำลังมากระดับยิ่งใหญ่ | |
เชิงเส้น | จริงๆแล้วเป็นพหุนามรูปแบบหนึ่ง แยกมาเรียกเพราะใช้บ่อย | |
พหุนาม | ยิ่งเลขชี้กำลังมากระดับยิ่งใหญ่ | |
เอกซ์โพเนนเชียล | ยิ่งค่าฐานมากยิ่งใหญ่ | |
แฟกทอเรียล | อาจรวมถึงการเรียงลำดับสับเปลี่ยน (permutation) | |
n ยกกำลัง n | มีบางครั้งคนใช้ O (nn) แทน O (n!) แต่ที่จริง O (nn) ใหญ่กว่า O (n!) เล็กน้อย |
บางครั้งเราจำเป็นต้องใช้การผสมโดยการคูณเช่น เกิดจากการคูณระหว่างเชิงเส้นและลอการิทึมย่อมทำได้
สัญกรณ์อื่น
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |