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

จากวิกิพีเดีย สารานุกรมเสรี
ตัวอย่างของสัญกรณ์โอใหญ่ โดย f(x) ∈ O(g(x)) ซึ่งหมายความว่ามี c > 0 (เช่น c = 1) และ x0 (เช่น x0 = 5) ที่ทำให้ f(x) < cg(x) เมื่อ x > x0

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

สัญกรณ์โอใหญ่ระบุลักษณะของฟังก์ชันตามอัตราการเติบโต ถึงแม้ฟังก์ชันจะต่างกัน แต่ถ้ามีอัตราการเติบโตเท่ากันก็จะมีสัญกรณ์โอใหญ่เท่ากัน สำหรับสัญกรณ์โอใหญ่แล้ว จะพิจารณาเฉพาะขอบเขตบนของอัตราการเติบโตของฟังก์ชัน อาทิฟังก์ชัน n^2+n และ n+4 ล้วนมีอัตราการเติบโตน้อยกว่าหรือเท่ากับ n^2 นั่นคืออัตราการเติบโตของฟังก์ชัน n^2 เป็นขอบเขตบนของ n^2+n และ n+4 จึงอาจกล่าวได้ว่า n^2+n และ n+4 เป็นสมาชิกของเซตของฟังก์ชัน O (n^2) ในขณะที่สัญกรณ์เชิงเส้นกำกับอื่น พิจารณาขอบเขตอื่น ๆ เช่นสัญกรณ์โอเมกาใหญ่พิจารณาขอบเขตล่างของอัตราการเติบโตของฟังก์ชันแทน

ประวัติ[แก้]

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

นิยาม[แก้]

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

ให้ f (n) และ g (n) เป็นฟังก์ชันบนจำนวนจริงใด ๆ แล้ว จะกล่าวว่า
f (n) \in O (g (n)) เมื่อ n\to\infty
ก็ต่อเมื่อมีจำนวนจริง c และ n_0 ค่าหนึ่งที่ทำให้  |f (n)|\le c|g (n)| ทุกๆ  n \ge n_0

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

ให้ f (x) และ g (x) เป็นฟังก์ชันใด ๆ จะกล่าวว่า
f (x) \in O (g (x)) ขณะ x เข้าใกล้ a
ก็ต่อเมื่อ \lim_{x\to a} \left|\frac{f (x) }{g (x) }\right| \in [0,\infty)

การขยายนิยามไปหลายตัวแปร[แก้]

นิยามทั้งสองรูปแบบสามารถขยายไปหลายตัวแปรได้

ให้ f (a_0,a_1,\ldots,a_n) และ g (a_0,a_1,\ldots,a_n) เป็นฟังก์ชันหลายตัวแปรใด ๆ จะกล่าวได้ว่า
f (a_0,a_1,\ldots,a_n) \in O (a_0,a_1,\ldots,a_n)
ก็ต่อเมื่อมีจำนวนจริง c และ n_0 ค่าหนึ่งที่ทำให้  |f (a_0,a_1,\ldots,a_n)|\le c |g (a_0,a_1,\ldots,a_n)| ทุก ๆ  a_0,a_1,\ldots,a_n \ge n_0

หรือในอีกนิยามที่พิจารณาอัตราการเติบโตของฟังก์ชันรอบๆพิกัด  (k_0,k_1,\ldots,k_n) ใดๆว่า

f (a_0,a_1,\ldots,a_n) \in O (g (a_0,a_1,\ldots,a_n))
ก็ต่อเมื่อ \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).

ตัวอย่าง[แก้]

  • n^2+n \le 2 n^2 ทุกๆ  n \ge 1 (หาได้จากการแก้อสมการ) เพราะฉะนั้น n^2+n \in O (n^2) (c=2 , n_0=1)
  • n^2+4 \le 2 n^2 ทุกๆ  n \ge 2 (หาได้จากการแก้อสมการ) เพราะฉะนั้น n^2+4 \in O (n^2) (c=2 , n_0=2)

หรือ

  •  \lim_{n\to\infty} \frac {n^2+n}{n^2} = 1 เพราะฉะนั้น n^2+n \in O (n^2)
  •  \lim_{n\to\infty} \frac {n^2+4}{n^2} = 1 เพราะฉะนั้น n^2+n \in O (n^2)

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

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

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

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

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

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

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

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

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

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

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

\left|e^x-\left (1+x+\frac{x^2}{2}\right) \right|  \in \hbox{O} (x^3) \qquad\hbox{as}\ x\to 0

คุณสมบัติ[แก้]

การคูณ[แก้]

การคูณด้วยค่าคงที่[แก้]

ให้ k เป็นค่าคงที่ใดๆ ที่เป็นบวก

O (k \cdot g) = O (g)
f\in O (g) \Rightarrow k\cdot f \in O (g)

การซ้อนสัญกรณ์โอใหญ่[แก้]

f (n) \in O (g (n)) \implies O (f (n)) \subset O (g (n))

ให้ h (n) เป็นอีกฟังก์ชันหนึ่ง

O (f (n)) \in O (g (n)) \implies O (f (h (n))) \subset O (g (h (n)))

สัญกรณ์โอใหญ่มาตรฐานน้อยสุด[แก้]

ในบางครั้งสัญกรณ์โอใหญ่อาจมีการครอบคลุมมากเกินไป เช่น  O (n^2) \subset O (n^3) เป็นต้น จึงทำให้สำหรับฟังก์ชันใดๆ อาจอยู่ในเซตของสัญกรณ์โอใหญ่หลายค่า จึงมีการกำหนดรูปแบบฟังก์ชันอย่างง่าย ให้ตอบในรูปสัญกรณ์โอใหญ่มาตรฐานน้อยสุด กล่าวคือตอบในรูปแบบมาตรฐานที่เล็กที่สุด เรามักจะอนุโลมให้ใช้จากสัญลักษณ์เท่ากับ (=) แทนสัญลักษณ์สมาชิก (\in) เมื่อใช้กับรูปสัญกรณ์โอใหญ่มาตรฐานน้อยสุดนี้ เช่น n^2+4 = O (n^2)

ในทางวิทยาการคอมพิวเตอร์ การทำงานที่มีสัญกรณ์โอใหญ่มาตรฐานน้อยสุดมีขนาดยิ่งเล็กเท่าใด แสดงว่าทำงานได้ยิ่งเร็วเท่านั้น

สัญกรณ์โอใหญ่มาตรฐานเรียงจากขนาดเล็กไปใหญ่ (ขนาดเล็กหมายถึงจะเป็นซับเซตของขนาดที่ใหญ่กว่า) ให้ m เป็นค่าคงที่ใดๆ ที่มากกว่าศูนย์ และ n เป็นโดเมนของฟังก์ชัน

สัญกรณ์โอใหญ่มาตรฐาน ชื่อฟังก์ชัน หมายเหตุ
O (1) ค่าคงที่ ไม่ใช้ค่าคงที่อื่นในการแสดงสัญกรณ์ เช่นไม่มีการใช้ O (2)
O (\log n) ลอการิทึม ลอการิทึมทุกฐานอยู่ในระดับเดียวกัน เพราะเปลี่ยนฐานได้โดยคูณค่าคงที่
O (k^n) 0<k<1 เอกซ์โพเนนเชียลฐานเศษส่วนแท้ ยิ่งค่าฐานมากยิ่งใหญ่
O ((\log n) ^m) โพลีลอการิทึม ยิ่งเลขชี้กำลังมากระดับยิ่งใหญ่
O (n^k) , 0<k<1 ยกกำลังที่เป็นเศษส่วนแท้ (ติดราก) ยิ่งเลขชี้กำลังมากระดับยิ่งใหญ่
O (n) เชิงเส้น จริงๆแล้วเป็นพหุนามรูปแบบหนึ่ง แยกมาเรียกเพราะใช้บ่อย
O (n^k) , k>1 พหุนาม ยิ่งเลขชี้กำลังมากระดับยิ่งใหญ่
O (k^n) k>1 เอกซ์โพเนนเชียล ยิ่งค่าฐานมากยิ่งใหญ่
O (n!) แฟกทอเรียล อาจรวมถึงการเรียงลำดับสับเปลี่ยน (permutation)
O (n^n) n ยกกำลัง n มีบางครั้งคนใช้ O (nn) แทน O (n!) แต่ที่จริง O (nn) ใหญ่กว่า O (n!) เล็กน้อย

บางครั้งเราจำเป็นต้องใช้การผสมโดยการคูณเช่น O (n log n) เกิดจากการคูณระหว่างเชิงเส้นและลอการิทึมย่อมทำได้

สัญกรณ์อื่น[แก้]