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

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

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

ข้อใดเติบโตช้าที่สุดเมื่อ n มีค่ามาก

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

เวลาทำงานในกรณีเฉลี่ยอธิบายสิ่งใด

1. Aเวลาสำหรับอินพุตที่มีความยาวเฉลี่ย
2. Bค่ากลางระหว่างเวลาทำงานในกรณีดีที่สุดกับกรณีเลวร้ายที่สุด
3. Cเวลาบนคอมพิวเตอร์ที่พบบ่อยที่สุด
4. Dเวลาคาดหมายภายใต้การแจกแจงของอินพุตขนาด n ที่กำหนด

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

1. AHeap sort
2. BSelection sort (แบบทั่วไป)
3. CQuicksort (แบบทำในที่เดิมทั่วไป)
4. DMerge sort

อัลกอริทึมของ Prim สร้างต้นไม้ทอดข้ามที่น้อยที่สุดอย่างไร

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

การโปรแกรมพลวัต (dynamic programming) มีประโยชน์เมื่อปัญหามี

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

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

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

การเรียงลำดับทอพอโลยีทำได้เฉพาะกับ

1. Aกราฟมีทิศทางแบบไม่มีวงจร (DAG)
2. Bกราฟบริบูรณ์
3. Cกราฟที่มีน้ำหนักติดลบ
4. Dกราฟไม่มีทิศทาง