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

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

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

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

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

เวลาทำงานในข้อใดเป็นพหุนาม

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

การกล่าวว่าอัลกอริทึม O(n²) เป็น O(n³) ด้วย ถูกต้องหรือไม่

1. Aถูกต้อง เพราะ Big O เป็นขอบเขตบน และ n² เติบโตไม่เร็วกว่า n³
2. Bถูกต้อง แต่เฉพาะเมื่อ n น้อยกว่า 100
3. Cไม่ถูก เพราะ n³ น้อยกว่า n² เมื่อ n มาก
4. Dไม่ถูก เพราะ Big O ต้องระบุอัตราการเติบโตที่แน่นอนของฟังก์ชันเสมอ

ในปัญหาการเลือกกิจกรรม กฎละโมบข้อใดให้จำนวนกิจกรรมที่ไม่ทับซ้อนกันมากที่สุดเสมอ

1. Aเลือกกิจกรรมที่สั้นที่สุดก่อน
2. Bเลือกกิจกรรมที่ทับซ้อนกับผู้อื่นน้อยที่สุดก่อน แล้วทำซ้ำกับกิจกรรมที่เข้ากันได้
3. Cเลือกกิจกรรมที่เสร็จเร็วที่สุด แล้วทำซ้ำกับกิจกรรมที่เข้ากันได้
4. Dเลือกกิจกรรมที่เริ่มเร็วที่สุด

ความซับซ้อนเชิงเวลาของ for i = 1 to n: (j = 1; while j < n: j = j × 2) คือเท่าใด

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

ปัญหาพนักงานขายเดินทางถูกจัดประเภทอย่างไร

1. Aตัดสินไม่ได้
2. Bแบบการตัดสินใจอยู่ใน P แต่แบบหาค่าเหมาะที่สุดเป็น NP-complete
3. Cอยู่ใน P เพราะอัลกอริทึมของ Dijkstra แก้ได้โดยเยี่ยมชมทุกเมืองหนึ่งครั้ง
4. Dแบบการตัดสินใจเป็น NP-complete และแบบหาค่าเหมาะที่สุดเป็น NP-hard

ปัญหา 0/1 knapsack ที่แก้ด้วยการโปรแกรมพลวัตใช้เวลา O(nW) เหตุใดจึงเรียกว่าเวลาแบบกึ่งพหุนาม (pseudo-polynomial)

1. AW เป็นตัวเลข เวลาจึงเป็นเอกซ์โพเนนเชียลเมื่อเทียบกับจำนวนบิตที่ใช้เขียน W
2. Bเพราะใช้ได้เฉพาะ W = 0
3. Cเพราะอัลกอริทึมเป็นแบบสุ่มและเวลาทำงานแปรผันไปตามอินพุตแต่ละครั้ง
4. Dเพราะ n มีค่าน้อยเสมอ