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

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

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

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

เนื้อหา

1 ประวัติ
2 นิยาม
- 2.1 นิยามแบบที่หนึ่ง
  - 2.1.1 ตัวอย่างจากนิยามนี้
  - 2.1.2 การขยายนิยามไปหลายตัวแปร
- 2.2 นิยามแบบที่สอง
  - 2.2.1 ตัวอย่างจากนิยามนี้
  - 2.2.2 การขยายนิยามไปหลายตัวแปร
3 การใช้งาน
- 3.1 กรณีเส้นกำกับอนันต์
- 3.2 กรณีเส้นกำกับกณิกนันต์
4 คุณสมบัติ
5 สัญกรณ์โอใหญ่มาตรฐานน้อยสุด

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

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

[แก้] นิยาม

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

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

[แก้] นิยามแบบที่หนึ่ง

ให้ f (n) และ g (n) เป็นฟังก์ชันใดๆ

$f (n) \in O (g (n))$ ก็ต่อเมื่อ

มีจำนวนจริง

c

และ

n 0

ค่าหนึ่งที่ทำให้

$|f (n)|\le c|g (n)|$ ทุกๆ $n \ge n_0$

[แก้] ตัวอย่างจากนิยามนี้

$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$ )

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

ให้ $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$

[แก้] นิยามแบบที่สอง

ให้ f (x) และ g (x) เป็นฟังก์ชันใดๆ

$f (x) \in O (g (x))$ ก็ต่อเมื่อ

$\lim_{x\rightarrow\infty} \frac {f (x) }{g (x) } \in [0,\infty)$

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

$f (x) \in O (g (x))$ ขณะ x เข้าใกล้ a ก็ต่อเมื่อ

$\lim_{x\to a} \left|\frac{f (x) }{g (x) }\right| \in [0,\infty).$

[แก้] ตัวอย่างจากนิยามนี้

$\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)$

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

ให้ $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 (g (a_0,a_1,\ldots,a_n))$ ก็ต่อเมื่อ

$\lim_{a_0,a_1,\ldots,a_n \to \infty } \frac {f (a_0,a_1,\ldots,a_n) }{g (a_0,a_1,\ldots,a_n) } \in [0,\infty)$

เช่นเดียวกันขยายไปถึงสัญกรณ์โอใหญ่กณิกนันต์ กล่าวคือพิจารณาอัตราการเติบโตของฟังก์ชันรอบๆพิกัด $(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 มีฟังก์ชันเป็น $T (n) = 4 n 2 - 2 n + 2$

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

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

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

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

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

$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$

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

[แก้] การบวก

$f_1 \in O (g_1) \ \wedge\ f_2\in O (g_2) \, \implies f_1 + f_2\in O (g_1 + g_2) \,$

บทเสริม $f_1 \in O (g) \land f_2 \in O (g) \implies f_1+f_2 \in O (g)$

$f + O (g) \in O (f + g)$

[แก้] การคูณ

$f_1 \in O (g_1) \ \wedge\ f_2\in O (g_2) \, \implies f_1 f_2\in O (g_1 g_2) \,$

$f\cdot O (g) \in O (f \cdot g)$

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

ให้ 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 (l o g n)$	ลอการิทึม	ลอการิทึมทุกฐานอยู่ในระดับเดียวกัน เพราะเปลี่ยนฐานได้โดยคูณค่าคงที่
$O (k n)$ 0<k<1	เอกซ์โพเนนเชียลฐานเศษส่วนแท้	ยิ่งค่าฐานมากยิ่งใหญ่
$O ((l o g 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 (nⁿ) แทน O (n!) แต่ที่จริง O (nⁿ) ใหญ่กว่า O (n!) เล็กน้อย

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

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

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

เนื้อหา

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

[แก้] นิยาม

[แก้] นิยามแบบที่หนึ่ง

[แก้] ตัวอย่างจากนิยามนี้

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

[แก้] นิยามแบบที่สอง

[แก้] ตัวอย่างจากนิยามนี้

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

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

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

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

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

[แก้] การบวก

[แก้] การคูณ

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

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

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

ดู

เครื่องมือส่วนตัว

ป้ายบอกทาง

สืบค้น

มีส่วนร่วม

เครื่องมือ

ภาษาอื่น