CoE KKU

โมเดลของการทำงานของอัลกอริทึมที่จะใช้เพื่อการวิเคราะห์อัลกอริทึมมีดังนี้

• เครื่องคอมพิวเตอร์ที่ใช้เป็นเครื่องคอมพิวเตอร์ธรรมดาที่การทำงานตาม instructions เป็นแบบ sequential (non-parallel)
• มี instructions มาตรฐาน เช่น addition, multiplication, comparison, และ assignment ที่ใช้เวลาในการทำงานเป็นหนึ่งหน่วยเวลา (one time unit) เท่านั้น
• โมเดลคอมพิวเตอร์ที่ใช้เป็นแบบ fixed size (เช่น 32-bit) integers และไม่มีการทำงานที่ซับซ้อนอื่น ๆ เช่น matrix inversion หรือ sorting ซึ่งแน่นอนว่าไม่สามารถทำให้แล้วเสร็จได้ในหนึ่งหน่วยเวลา
• เครื่องคอมพิวเตอร์ที่ใช้มีหน่วยความจำไม่จำกัด (infinite memory) ถ้าเป็นกรณีอื่น ๆ ก็จะระบุอย่างชัดเจน

โมเดลที่ใช้ดังกล่าวนี้ก็มีจุดอ่อนเช่นกัน เช่น ในชีวิตจริง การทำงานตาม instruction ไม่ได้ใช้เวลาเท่ากัน โดยเฉพาะอย่างยิ่งการอ่านจานแม่เหล็กหนึ่งครั้งนับเวลาเท่ากับการทำงานการบวกหนึ่งครั้ง (ถ้าไม่ระบุเป็นอย่างอื่น) ซึ่งความจริงการทำงานการบวกเร็วกว่ามากหลายเท่า นอกจากนั้นการถือว่ามีหน่วยความจำไม่จำกัดก็หมายความว่าเราจะไม่พบกับปัญหา page fault ซึ่งเป็นปัญหาที่เกิดขึ้นจริงได้