ใบงาน อัลกอริทึมและความซับซ้อน พร้อมเฉลย

อัลกอริทึมที่มีลูปซ้อนกันสองชั้น แต่ละชั้นทำงาน n รอบ โดยทั่วไปมีความซับซ้อนเท่าใด

1. AO(n²)
2. BO(2n)
3. CO(log n)
4. DO(n)

อัลกอริทึม O(n) ใช้เวลา 3 วินาทีเมื่อ n = 1 ล้าน เมื่อ n = 2 ล้านจะใช้เวลาประมาณเท่าใด

1. A12 วินาที
2. B9 วินาที
3. C3 วินาที
4. D6 วินาที

อัลกอริทึมคืออะไร

1. Aโครงสร้างข้อมูลที่เก็บตัวเลข
2. Bโปรแกรมคอมพิวเตอร์ใด ๆ ที่มีส่วนต่อประสานกราฟิก
3. Cลำดับขั้นตอนจำกัดที่นิยามชัดเจนซึ่งแก้ปัญหาหนึ่ง
4. Dภาษาโปรแกรมที่ออกแบบมาสำหรับเขียนสูตรทางคณิตศาสตร์

เหตุใดจึงมักละฐานของลอการิทึมใน Big O เช่น O(log n)

1. Aลอการิทึมทั้งหมดในวิทยาการคอมพิวเตอร์มีฐาน 10 จึงไม่ต้องระบุ
2. Bลอการิทึมที่ฐานต่างกันต่างกันเพียงตัวคูณคงที่
3. Cลอการิทึมถูกปัดเป็นจำนวนเต็มเสมอ
4. Dฐานมีความสำคัญเฉพาะเมื่อ n น้อย

ขอบเขตล่างของการเรียงลำดับแบบเปรียบเทียบในกรณีเลวร้ายที่สุดคือ

1. AΩ(n²)
2. BΩ(n log n)
3. CΩ(log n)
4. DΩ(n)

การค้นหาแบบทวิภาคต้องเปรียบเทียบประมาณกี่ครั้งในกรณีเลวร้ายที่สุดบนอาร์เรย์ที่เรียงแล้วซึ่งมี 1,000,000 สมาชิก

1. Aประมาณ 20
2. Bประมาณ 1,000
3. Cประมาณ 100
4. Dประมาณ 500,000

ข้อใดเกี่ยวกับสัญกรณ์ little-o ถูกต้อง

1. An = o(n) เพราะทุกฟังก์ชันเป็น little-o ของตัวมันเอง
2. B2n = o(n) เพราะ 2n เติบโตช้า
3. Cn = o(n²) แต่ n ไม่ใช่ o(n)
4. Dn² = o(n)

2²ⁿ อยู่ใน O(2ⁿ) หรือไม่

1. Aไม่ เพราะ 2²ⁿ = 4ⁿ และ 4ⁿ / 2ⁿ = 2ⁿ เติบโตไม่มีขอบเขต
2. Bใช่ เพราะตัวคูณคงที่ในเลขชี้กำลังถูกละไว้เสมอใน Big O
3. Cไม่ เพราะ 2²ⁿ เติบโตช้ากว่า 2ⁿ
4. Dใช่ เพราะทั้งสองเป็นเอกซ์โพเนนเชียล