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

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

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

f(n) = Θ(g(n)) หมายความว่าอย่างไร

1. Af เติบโตช้ากว่า g อย่างเด็ดขาด
2. Bf เติบโตในอัตราเดียวกับ g โดยถูกจำกัดทั้งบนและล่างด้วยผลคูณคงที่ของ g
3. Cf น้อยกว่า g เสมอทุกค่า n ดังนั้น g เป็นขอบเขตบนของ f แต่ไม่เคยเป็นขอบเขตล่าง
4. Df เติบโตเร็วกว่า g อย่างเด็ดขาด

selection sort ทำงานอย่างไร

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

อัลกอริทึม Floyd–Warshall คำนวณอะไรและเร็วเพียงใด

1. Aเส้นทางสั้นที่สุดระหว่างจุดยอดทุกคู่ใน O(V³)
2. Bเส้นทางสั้นที่สุดจากจุดยอดต้นทางหนึ่งไปยังจุดยอดอื่นทั้งหมดใน O(V + E)
3. Cต้นไม้ทอดข้ามที่น้อยที่สุดใน O(E log V)
4. Dลำดับทอพอโลยีใน O(V²)

การที่ปัญหามีโครงสร้างย่อยเหมาะสมที่สุด (optimal substructure) หมายความว่าอย่างไร

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

การค้นหาแบบทวิภาคต้องเปรียบเทียบประมาณกี่ครั้งในกรณีเลวร้ายที่สุดบนอาร์เรย์ที่เรียงแล้วซึ่งมี 1,000,000 สมาชิก

1. Aประมาณ 1,000
2. Bประมาณ 20
3. Cประมาณ 100
4. Dประมาณ 500,000

นิยามใดของคลาส P ถูกต้อง

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

การเลือกปลายทั้งสองของทุกเส้นเชื่อมใน maximal matching ให้ผลเป็นเซตครอบคลุมจุดยอด (vertex cover) เซตครอบคลุมนี้ดีเพียงใด

1. Aเป็นเซตครอบคลุมจุดยอดที่เล็กที่สุดเสมอ
2. Bขนาดไม่เกินสองเท่าของเซตครอบคลุมจุดยอดที่เล็กที่สุด
3. Cไม่เกิน log n เท่าของค่าต่ำสุด
4. Dไม่ทราบคุณภาพเมื่อเทียบกับค่าที่เหมาะสมที่สุด