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

การเข้าถึงสมาชิกในอาร์เรย์ด้วยดัชนีใช้เวลา

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

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

1. A9 วินาที
2. B6 วินาที
3. C12 วินาที
4. D3 วินาที

memoisation คืออะไร

1. Aการเขียนคอมเมนต์ข้างทุกบรรทัดของโค้ด
2. Bการแปลงการเรียกซ้ำเป็นลูปที่เทียบเท่ากันโดยอัตโนมัติ จึงไม่ต้องใช้สแต็กการเรียก
3. Cการคืนหน่วยความจำหลังฟังก์ชันทำงานเสร็จ
4. Dการเก็บผลลัพธ์ของการเรียกฟังก์ชันเพื่อตอบการเรียกซ้ำจากหน่วยความจำ

อัลกอริทึมการเรียงลำดับใดเป็นแบบเสถียร (stable)

1. ASelection sort (แบบทั่วไป)
2. BQuicksort (แบบทำในที่เดิมทั่วไป)
3. CMerge sort
4. DHeap sort

การเรียกซ้ำของ merge sort สำหรับอาร์เรย์ n สมาชิกมีกี่ระดับ

1. Aประมาณ n / 2
2. Bประมาณ n
3. Cประมาณ log₂ n
4. Dประมาณ √n

ความสัมพันธ์เวียนเกิด T(n) = 2T(n/2) + O(n) มีผลเฉลยเป็น

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

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

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

ปัญหาหนึ่งเป็น NP-complete ถ้ามัน

1. Aอยู่นอก NP แต่ยากกว่าทุกปัญหา NP เช่น ปัญหาการหยุด
2. Bอยู่ใน NP และทุกปัญหา NP ลดรูปมาเป็นมันได้ในเวลาพหุนาม
3. Cแก้ไม่ได้เลย
4. Dแก้ได้ในเวลาพหุนาม