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

ถ้าการดำเนินการหนึ่งทำงานในเวลา O(1) หมายความว่าอย่างไร

1. Aประมวลผลหนึ่งสมาชิกต่อวินาทีของเวลาทำงานพอดี
2. Bใช้เวลาหนึ่งวินาทีพอดีเสมอ
3. Cรันได้เพียงครั้งเดียว
4. Dเวลาทำงานไม่เพิ่มตามขนาดอินพุต

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

1. A2 วินาที
2. B4 วินาที
3. C8 วินาที
4. D1 วินาที

การเติบโตแบบ O(2ⁿ) เรียกว่าอะไร

1. Aลอการิทึม
2. Bพหุนาม
3. Cเชิงเส้น
4. Dเอกซ์โพเนนเชียล

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

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

คุณเรียงอาร์เรย์ n สมาชิกหนึ่งครั้ง แล้วตอบคำถามการเป็นสมาชิก k ข้อด้วยการค้นหาแบบทวิภาค ต้นทุนรวมเท่าใด

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

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

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

เหตุใดการค้นหาแบบเปรียบเทียบใด ๆ ในอาร์เรย์ที่เรียงแล้วจึงต้องใช้ Ω(log n) การเปรียบเทียบในกรณีเลวร้ายที่สุด

1. Aการค้นหาแบบทวิภาคเป็นอัลกอริทึมเดียวที่เป็นไปได้ และต้องใช้ log₂ n การเปรียบเทียบ
2. Bการเปรียบเทียบแต่ละครั้งใช้เวลาแบบลอการิทึม
3. Cทุกสมาชิกต้องถูกเปรียบเทียบอย่างน้อยหนึ่งครั้ง
4. Dต้นไม้ตัดสินใจที่มีผลลัพธ์ที่เป็นไปได้ n แบบต้องมีความลึกอย่างน้อย log₂ n

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

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