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

เราจะนิยาม '''ความซับซ้อนด้านเวลา''' (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> บนเครื่องอื่นๆด้วยเช่นกัน จะเห็นได้ว่าสัญกรณ์สัญลักณ์โอใหญ่ช่วยเราหลีกเลี่ยงการกล่าวถึงรายละเอียด ที่เป็นความแตกต่างระหว่างเครื่องคอมพิวเตอร์