ผลต่างระหว่างรุ่นของ "สัญกรณ์โอใหญ่"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล สังคายนาวิกิพีเดียไทยรอบ 2 +เก็บกวาดด้วยสจห. |
|||
บรรทัด 1:
{{ต้องการอ้างอิง}}
ในวิชา[[ทฤษฎีความซับซ้อน]]และ[[คณิตศาสตร์]] '''สัญกรณ์โอใหญ่''' ({{lang-en|Big O notation}}) เป็น[[สัญกรณ์คณิตศาสตร์]]ที่ใช้บรรยาย[[พฤติกรรมเชิงเส้นกำกับ]]ของ[[ฟังก์ชัน]] โดยระบุเป็น[[ขนาด]] (magnitude) ของฟังก์ชันใน[[พจน์ (คณิตศาสตร์)|พจน์]]ของฟังก์ชันอื่นที่โดยทั่วไปซับซ้อนน้อยกว่า อาทิฟังก์ชัน <math>n^2+n</math> และ <math>n^2+4</math> ล้วนมีอัตราการเติบโตเดียวกับ <math>n^2</math> เราจะกล่าวได้ว่า <math>n^2+n</math> และ <math>n^2+4</math> เป็นสมาชิกของเซตของฟังก์ชัน <math>O (n^2) </math>
สัญกรณ์โอใหญ่ใช้ในการเขียนเพื่อประมาณ[[พจน์ (คณิตศาสตร์)|พจน์]]ใน[[คณิตศาสตร์]] และประยุกต์ใช้ใน[[วิทยาการคอมพิวเตอร์]]เพื่อใช้อธิบายความเร็วในการทำงาน[[โปรแกรม]]
บรรทัด 14:
=== นิยามแบบที่หนึ่ง ===
ให้ f (n) และ g (n) เป็น[[ฟังก์ชัน]]ใดๆ
:<math>f (n) \in O (g (n)) </math> ก็ต่อเมื่อ
:มีจำนวนจริง <math>c</math> และ <math>n_0</math> ค่าหนึ่งที่ทำให้
:<math> |f (n)|\le c|g (n)| </math> ทุกๆ <math> n \ge n_0 </math>
บรรทัด 23:
==== การขยายนิยามไปหลายตัวแปร ====
ให้ <math>f (a_0,a_1,\ldots,a_n) </math> และ <math>g (a_0,a_1,\ldots,a_n) </math> เป็น[[ฟังก์ชัน]]หลายตัวแปรใดๆ
:<math>f (a_0,a_1,\ldots,a_n) \in O (a_0,a_1,\ldots,a_n) </math> ก็ต่อเมื่อ
:มีจำนวนจริง <math>c</math> และ <math>n_0</math> ค่าหนึ่งที่ทำให้
บรรทัด 30:
=== นิยามแบบที่สอง ===
ให้ f (x) และ g (x) เป็น[[ฟังก์ชัน]]ใดๆ
:<math>f (x) \in O (g (x)) </math> ก็ต่อเมื่อ
:<math> \lim_{x\rightarrow\infty} \frac {f (x) }{g (x) } \in [0,\infty) </math>
ในนิยามนี้สามารถขยายไปถึงสัญกรณ์โอใหญ่กณิกนันต์ กล่าวคือพิจารณาอัตรากการเติบโตของฟังกชันรอบๆจุด a ใดๆว่า
:<math>f (x) \in O (g (x)) </math> ขณะ x เข้าใกล้ a ก็ต่อเมื่อ
::<math>\lim_{x\to a} \left|\frac{f (x) }{g (x) }\right| \in [0,\infty).</math>
==== ตัวอย่างจากนิยามนี้ ====
บรรทัด 40:
==== การขยายนิยามไปหลายตัวแปร ====
ให้ <math>f (a_0,a_1,\ldots,a_n) </math> และ <math>g (a_0,a_1,\ldots,a_n) </math> เป็น[[ฟังก์ชัน]]หลายตัวแปรใดๆ
:<math>f (a_0,a_1,\ldots,a_n) \in O (g (a_0,a_1,\ldots,a_n)) </math> ก็ต่อเมื่อ
:<math> \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) </math>
เช่นเดียวกันขยายไปถึงสัญกรณ์โอใหญ่กณิกนันต์ กล่าวคือพิจารณาอัตราการเติบโตของฟังก์ชันรอบๆพิกัด <math> (k_0,k_1,\ldots,k_n) </math> ใดๆว่า
:<math>f (a_0,a_1,\ldots,a_n) \in O (g (a_0,a_1,\ldots,a_n)) </math> ก็ต่อเมื่อ
::<math>\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).</math>
บรรทัด 67:
หมายความว่า เมื่อ ''x'' มีค่าเข้าใกล้ศูนย์ ผลต่างของฟังก์ชัน<math> e^x</math> กับ <math>1+x+x^2/2</math> (หรืออาจกล่าวอีกนัยหนึ่งว่าเป็นความคลาดเคลื่อนของสองฟังก์ชันนี้) จะมีอยู่ในสับเซตของ<math>O (x^3) </math>นั่นเอง หรือเขียนเป็นสัญลักษณ์ว่า
:<math>\left|e^x-\left (1+x+\frac{x^2}{2}\right) \right| \in \hbox{O} (x^3) \qquad\hbox{as}\ x\to 0</math>
== คุณสมบัติ ==
บรรทัด 89:
=== การซ้อนสัญกรณ์โอใหญ่ ===
:<math>f (n) \in O (g (n)) \implies O (f (n)) \subset O (g (n)) </math>
ให้ h (n) เป็นอีกฟังก์ชันหนึ่ง
:<math>O (f (n)) \in O (g (n)) \implies O (f (h (n))) \subset O (g (h (n))) </math>
== สัญกรณ์โอใหญ่มาตรฐานน้อยสุด ==
| |||