ผลต่างระหว่างรุ่นของ "สัญกรณ์โอใหญ่"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล Bot: Migrating 29 interwiki links, now provided by Wikidata on d:q269878 (translate me) ป้ายระบุ: ลบลิงก์ข้ามภาษา |
ไม่มีความย่อการแก้ไข ป้ายระบุ: การแก้ไขแบบเห็นภาพ แก้ไขจากอุปกรณ์เคลื่อนที่ แก้ไขจากเว็บสำหรับอุปกรณ์เคลื่อนที่ |
||
บรรทัด 1:
{{ต้องการอ้างอิง}}
[[File:Big-O-notation.png|400px|thumb|ตัวอย่างของสัญกรณ์โอใหญ่ โดย ''f''(''x'') ∈ O(''g''(''x'')) ซึ่งหมายความว่ามี ''c'' > 0 (เช่น ''c'' = 1) และ ''x''<sub>0</sub> (เช่น ''x''<sub>0</sub> = 5) ที่ทำให้ ''f''(''x'') < ''cg''(''x'') เมื่อ ''x'' > ''x''<sub>0</sub>]]
ในวิชา[[ทฤษฎีความซับซ้อนในการคำนวณ|ทฤษฎีความซับซ้อน]]และ[[คณิตศาสตร์]] '''สัญกรณ์โอใหญ่''' ({{lang-en|Big O notation}}) เป็น[[สัญกรณ์คณิตศาสตร์]]ที่ใช้บรรยาย[[พฤติกรรมเชิงเส้นกำกับ]]ของ[[ฟังก์ชัน (คณิตศาสตร์)|ฟังก์ชัน]] โดยระบุเป็น[[ขนาด]] (magnitude) ของฟังก์ชันใน[[พจน์ (คณิตศาสตร์)|พจน์]]ของฟังก์ชันอื่นที่โดยทั่วไปซับซ้อนน้อยกว่า สัญกรณ์โอใหญ่เป็นหนึ่งใน'''[[สัญกรณ์เชิงเส้นกำกับ]]''' หรืออาจเรียกว่า '''สัญกรณ์ของลันเดา''' หรือ '''สัญกรณ์ของบัคแมนน์-ลันเดา''' (ตั้งชื่อตาม[[เอ็ดมุนด์ ลานเดา]]และ[[เพาล์ บาคมันน์]]) สัญกรณ์โอใหญ่ใช้ในการเขียนเพื่อประมาณ[[พจน์ (คณิตศาสตร์)|พจน์]]ใน[[คณิตศาสตร์]] ประยุกต์ใช้ใน[[วิทยาการคอมพิวเตอร์]]เพื่อใช้อธิบายความเร็วประมาณในการทำงานของ[[โปรแกรม]]ในกรณีต้องประมวลผล[[ข้อมูล]]จำนวนมาก และใช้เพื่ออธิบายประสิทธิภาพของ[[ขั้นตอนวิธี]]หรือ[[โครงสร้างข้อมูล]]นั้น ๆ
สัญกรณ์โอใหญ่ระบุลักษณะของฟังก์ชันตามอัตราการเติบโต ถึงแม้ฟังก์ชันจะต่างกัน แต่ถ้ามีอัตราการเติบโตเท่ากันก็จะมีสัญกรณ์โอใหญ่เท่ากัน สำหรับสัญกรณ์โอใหญ่แล้ว จะพิจารณาเฉพาะ[[ขอบเขตบน]]ของอัตราการเติบโตของฟังก์ชัน อาทิฟังก์ชัน <math>n^2+n</math> และ <math>n+4</math> ล้วนมีอัตราการเติบโต''น้อยกว่า''หรือ''เท่ากับ'' <math>n^2</math> นั่นคืออัตราการเติบโตของฟังก์ชัน <math>n^2</math> เป็นขอบเขตบนของ <math>n^2+n</math> และ <math>n+4</math> จึงอาจกล่าวได้ว่า <math>n^2+n</math> และ <math>n+4</math> เป็นสมาชิกของเซตของฟังก์ชัน <math>O (n^2) </math> ในขณะที่สัญกรณ์เชิงเส้นกำกับอื่น พิจารณาขอบเขตอื่น ๆ เช่น[[สัญกรณ์โอเมกาใหญ่]]พิจารณา[[ขอบเขตล่าง]]ของอัตราการเติบโตของฟังก์ชันแทน
บรรทัด 96:
สัญกรณ์โอใหญ่มาตรฐานเรียงจากขนาดเล็กไปใหญ่ (ขนาดเล็กหมายถึงจะเป็นซับเซตของขนาดที่ใหญ่กว่า)
ให้ m เป็นค่าคงที่ใดๆ ที่มากกว่าศูนย์ และ n เป็นโดเมนของฟังก์ชัน
{| class="wikitable sortable mw-collapsible mw-collapsed"
|+
!สัญกรณ์โอใหญ่มาตรฐาน!!ชื่อฟังก์ชัน !!หมายเหตุ
|-
| |||