ผลต่างระหว่างรุ่นของ "ทฤษฎีความซับซ้อนในการคำนวณ"

(โรบอต แก้ไข: ro:Teoria complexității)
คำถามใดๆ คำถามหนึ่งจะถูกเรียกว่า "ตัวอย่างปัญหา" (instance) ในกรณีนี้ เราจะเรียก "จงหาตัวประกอบที่เป็นจำนวนเฉพาะของ 15" ว่าเป็นตัวอย่างปัญหาของปัญหาแยกตัวประกอบ
 
เราจะนิยาม '''ความซับซ้อนด้านเวลา''' (time complexity) สำหรับปัญหาหนึ่ง ๆ ว่าเป็นจำนวนขั้นตอนที่ใช้ในการแก้ตัวอย่างปัญหาสำหรับปัญหานั้น ในรูปฟังก์ชันของ[[ขนาดของปัญหา|ขนาดของข้อมูลป้อนเข้า]] (ซึ่งโดยปกติแล้วเราจะคิดขนาดเป็น[[บิต]]) โดยใช้ขั้นตอนวิธีที่มีประสิทธิภาพที่สุด ยกตัวอย่างเช่น ในปัญหา ๆ หนึ่ง สำหรับทุกตัวอย่างปัญหาที่มีขนาด <math>n</math> บิต ถ้าเราสามารถแก้ตัวอย่างปัญหานี้ได้ภายใน <math>n^2</math> ขั้นตอน เราสามารถพูดได้ว่าปัญหานี้มีความซับซ้อนด้านเวลาเป็น <math>n^2</math> ซึ่งในการกล่าวถึงเวลาที่ใช้นั้น แน่นอนว่าเครื่องจักร หรือ คอมพิวเตอร์แต่ละเครื่องก็ใช้เวลาในการคำนวณแตกต่างกันไป เพื่อที่จะหลีกเลี่ยงความแตกต่างในจุดนี้ เราจะใช้[[สัญกรณ์โอใหญ่สัญลักณ์โอใหญ่]] (Big O notation) ปัญหาที่มีความซับซ้อนด้านเวลาเป็น <math>O(n^2)</math> ในเครื่องคอมพิวเตอร์เครื่องหนึ่ง จะมีความซับซ้อนด้านเวลาเป็น <math>O(n^2)</math> บนเครื่องอื่นๆด้วยเช่นกัน จะเห็นได้ว่าสัญกรณ์โอใหญ่ช่วยเราหลีกเลี่ยงการกล่าวถึงรายละเอียด ที่เป็นความแตกต่างระหว่างเครื่องคอมพิวเตอร์
 
หลายครั้งเราจะกล่าวถึงความซับซ้อนด้านเวลาว่าเป็น "เวลาที่ใช้ในการแก้ปัญหา" หรือ "เวลาที่ใช้ในการทำงาน"
ผู้ใช้นิรนาม