การวิเคราะห์เชิงเส้นกำกับ

การวิเคราะห์เชิงเส้นกำกับอธิบายว่าเวลาทำงานหรือหน่วยความจำของอัลกอริทึมเพิ่มขึ้นอย่างไรเมื่อขนาดอินพุตมีขนาดใหญ่ขึ้น โดยใช้สัญกรณ์ เช่น big-O, big-Omega และ big-Theta เพื่อจับอัตราการเติบโตในขณะที่ละเว้นค่าคงที่และพจน์ลำดับต่ำกว่า

Definition

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

Scope

หัวข้อนี้ครอบคลุมสัญกรณ์เชิงเส้นกำกับที่ใช้ในการกำหนดลักษณะการใช้ทรัพยากร — big-O (ขอบเขตบน), big-Omega (ขอบเขตล่าง), big-Theta (ขอบเขตที่กระชับ), และ little-o และ little-omega ที่เข้มงวด — พร้อมด้วยคลาสการเติบโตมาตรฐาน (ค่าคงที่, ลอการิทึม, เชิงเส้น, เชิงเส้นลอการิทึม, พหุนาม, เอ็กซ์โพเนนเชียล) และกฎสำหรับการจัดการขอบเขตเหล่านี้ นอกจากนี้ยังกล่าวถึงเหตุผลที่ปัจจัยคงที่และพจน์ลำดับต่ำกว่าถูกละทิ้ง และวิธีการเปรียบเทียบเชิงเส้นกำกับทำนายพฤติกรรมการปรับขนาด หัวข้อนี้ไม่รวมกลไกการแก้ความสัมพันธ์เวียนบังเกิดที่ใช้ในการหาขอบเขตเหล่านี้ ซึ่งจะกล่าวถึงแยกต่างหาก

Core questions

• big-O, big-Omega และ big-Theta แต่ละตัวยืนยันอะไรเกี่ยวกับการเติบโตของฟังก์ชัน?
• ทำไมปัจจัยคงที่และพจน์ลำดับต่ำกว่าจึงถูกละเว้นในการเปรียบเทียบเชิงเส้นกำกับ?
• คลาสการเติบโตทั่วไปเรียงลำดับจากช้าที่สุดไปเร็วที่สุดอย่างไร?
• ขอบเขตเชิงเส้นกำกับทำนายว่าอัลกอริทึมจะปรับขนาดสำหรับอินพุตขนาดใหญ่อย่างไร?
• เมื่อใดที่อัลกอริทึมที่ช้ากว่าเชิงเส้นกำกับยังคงเป็นที่ต้องการในทางปฏิบัติ?

Key concepts

• สัญกรณ์ big-O
• สัญกรณ์ big-Omega
• สัญกรณ์ big-Theta
• little-o และ little-omega
• คลาสการเติบโต
• ปัจจัยคงที่
• พจน์ลำดับต่ำกว่า
• ความสามารถในการปรับขนาด

Key theories

สัญกรณ์ลำดับ

Big-O กำหนดขอบเขตบนของฟังก์ชันภายในปัจจัยคงที่, big-Omega กำหนดขอบเขตล่าง, และ big-Theta กำหนดขอบเขตทั้งสองทาง; คำจำกัดความเหล่านี้ซึ่ง Knuth ได้กำหนดมาตรฐานสำหรับวิทยาการคอมพิวเตอร์ ให้ภาษาที่แม่นยำสำหรับอัตราการเติบโต

การครอบงำของอัตราการเติบโต

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

Clinical relevance

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

History

สัญกรณ์ big-O และที่เกี่ยวข้องมีต้นกำเนิดในทฤษฎีจำนวนเชิงวิเคราะห์ในศตวรรษที่ 19 โดย Bachmann และ Landau (จึงเรียกว่า 'สัญกรณ์ Landau') Donald Knuth ได้ปรับใช้และกำหนดมาตรฐานสำหรับการวิเคราะห์อัลกอริทึมในช่วงทศวรรษ 1960 และ 1970 รวมถึงบันทึกในปี 1976 ที่ชี้แจงการใช้ big-Omega และ big-Theta ในวิทยาการคอมพิวเตอร์

Key figures

• Donald Knuth
• Paul Bachmann
• Edmund Landau

Seminal works

• knuth1976bigo
• cormen2009

Frequently asked questions

big-O ที่เล็กกว่าหมายถึงอัลกอริทึมที่เร็วกว่าเสมอไปหรือไม่?

ไม่จำเป็นสำหรับขนาดอินพุตที่กำหนด Big-O อธิบายการเติบโตเมื่อขนาดอินพุตมีค่าเข้าใกล้ infinity และซ่อนปัจจัยคงที่ ดังนั้นอัลกอริทึมที่มีคลาสเชิงเส้นกำกับที่แย่กว่าอาจเร็วกว่าสำหรับอินพุตขนาดเล็ก เป็นแนวทางที่ดีกว่าสำหรับอินพุตขนาดใหญ่และความสามารถในการปรับขนาด

ความแตกต่างระหว่าง big-O และ big-Theta คืออะไร?

Big-O ให้เพียงขอบเขตบนของการเติบโต ดังนั้นจึงระบุว่าอัลกอริทึมไม่แย่ไปกว่าอัตราที่กำหนด Big-Theta ให้ขอบเขตที่กระชับ โดยยืนยันว่าการเติบโตตรงกับอัตรานั้นทั้งบนและล่าง การกล่าวว่าอัลกอริทึมเป็น Theta(n log n) เป็นข้อความที่แข็งแกร่งและแม่นยำกว่า O(n log n)