ความซับซ้อนของอัลกอริทึมคืออะไร?

ความซับซ้อนของอัลกอริทึม (ความซับซ้อนในการคำนวณหรือความซับซ้อนของ Kolmogorov) เป็นแนวคิดพื้นฐานในทฤษฎีความซับซ้อนของการคำนวณและทฤษฎีข้อมูลอัลกอริทึมและมีบทบาทสำคัญในการเหนี่ยวนำอย่างเป็นทางการความซับซ้อนของอัลกอริทึมของสตริงไบนารีถูกกำหนดให้เป็นโปรแกรมที่สั้นที่สุดและมีประสิทธิภาพมากที่สุดที่สามารถสร้างสตริงได้แม้ว่าจะมีจำนวนโปรแกรมที่ไม่สิ้นสุดที่สามารถสร้างสตริงที่กำหนดได้ แต่โปรแกรมหนึ่งหรือกลุ่มของโปรแกรมจะสั้นที่สุดเสมอไม่มีวิธีอัลกอริทึมในการค้นหาอัลกอริทึมที่สั้นที่สุดที่ส่งออกสตริงที่กำหนดนี่เป็นหนึ่งในผลลัพธ์แรกของทฤษฎีความซับซ้อนในการคำนวณถึงกระนั้นเราก็สามารถคาดเดาได้ผลลัพธ์นี้ (ความซับซ้อนในการคำนวณของสตริง) กลายเป็นสิ่งสำคัญมากสำหรับการพิสูจน์ที่เกี่ยวข้องกับการคำนวณ

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

การเกิดขึ้น

, วิวัฒนาการและอัจฉริยะกับวัตถุที่ผลิตโดยแต่ละการดูแลความซับซ้อนอัลกอริทึมที่มากขึ้นความซับซ้อนในการคำนวณเป็นความคิดที่ใช้บ่อยในวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีเพื่อกำหนดความยากลำบากในการคำนวณการแก้ปัญหาของปัญหาทางคณิตศาสตร์และตรรกะมีคลาสความซับซ้อนมากกว่า 400 คลาสและมีการค้นพบคลาสเพิ่มเติมอย่างต่อเนื่องคำถามที่มีชื่อเสียง p ' np

คำถามเกี่ยวข้องกับธรรมชาติของสองคลาสความซับซ้อนเหล่านี้คลาสที่ซับซ้อนรวมถึงปัญหาที่ยากกว่าสิ่งที่อาจเผชิญในคณิตศาสตร์จนถึงแคลคูลัสมีปัญหามากมายที่จินตนาการได้ในทฤษฎีความซับซ้อนในการคำนวณซึ่งจะต้องใช้เวลาในการแก้ปัญหาที่ใกล้เคียงกันในระยะเวลาใกล้ชิด

ความซับซ้อนของอัลกอริทึมและแนวคิดที่เกี่ยวข้องได้รับการพัฒนาในทศวรรษ 1960 โดยนักวิจัยหลายสิบคนAndrey Kolmogorov, Ray Solomonoff และ Gregory Chaitin มีส่วนร่วมที่สำคัญในช่วงปลายยุค 60 ด้วยทฤษฎีข้อมูลอัลกอริทึมหลักการของความยาวข้อความขั้นต่ำที่เกี่ยวข้องอย่างใกล้ชิดกับความซับซ้อนของอัลกอริทึมให้รากฐานของการอนุมานทางสถิติและอุปนัยและการเรียนรู้ของเครื่อง