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

ความซับซ้อนเชิงพื้นที่ (space complexity) วัดสิ่งใด

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

counting sort สำหรับจำนวนเต็ม n ตัวในช่วง 0 ถึง k ใช้เวลาเท่าใด

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

การค้นหาแบบทวิภาคต้องการอะไรจากอินพุต

1. Aความยาวอาร์เรย์ต้องเป็นเลขกำลังสอง
2. Bอาร์เรย์ต้องเรียงลำดับแล้ว
3. Cอาร์เรย์ต้องมีแต่จำนวนบวก
4. Dอาร์เรย์ต้องมีสมาชิกไม่เกิน 1000 ตัว

เหตุใดการโปรแกรมพลวัตจึงไม่ช่วยเร่ง merge sort ได้จริง

1. AMerge sort ไม่มีโครงสร้างแบบเรียกซ้ำ
2. Bปัญหาย่อยของมันไม่ซ้อนทับกัน จึงไม่มีอะไรให้ใช้ซ้ำ
3. Cการโปรแกรมพลวัตใช้ได้กับปัญหากราฟเท่านั้น ไม่ใช่กับอาร์เรย์
4. DMerge sort เป็น O(n) อยู่แล้ว

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

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

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

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

การคูณแบบ Karatsuba ตรงตาม T(n) = 3T(n/2) + O(n) ผลเฉลยคืออะไร

1. AΘ(n³)
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(n^{log₂ 3}) ประมาณ n^1.585

อัลกอริทึมการโปรแกรมพลวัตของ Held–Karp แก้ปัญหาพนักงานขายเดินทางได้อย่างแม่นยำ เวลาทำงานสำหรับ n เมืองคือเท่าใด

1. AO(n² 2ⁿ)
2. BO(n³)
3. CO(n!)
4. DO(2^n²)