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

memoisation คืออะไร

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

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

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

สัญกรณ์ใดใช้อธิบายขอบเขตบนของอัตราการเติบโต

1. ABig O
2. BBig Omega
3. CBig Theta
4. DLittle omega

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

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

การค้นหาในแนวกว้าง (BFS) บนกราฟที่ไม่มีน้ำหนักให้ผลเป็น

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

ความซับซ้อนเชิงเวลาของฟีโบนักชีแบบเรียกซ้ำตรง ๆ (fib(n) = fib(n−1) + fib(n−2)) คือ

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

ข้อใดเกี่ยวกับการเลือกสมาชิกที่เล็กที่สุดอันดับที่ k ของอาร์เรย์ที่ไม่เรียงลำดับถูกต้อง

1. Aการเลือกทำได้ใน O(n²) เท่านั้น
2. BQuickselect ทำงานใน O(log n) ในกรณีเลวร้ายที่สุด เพราะเรียกซ้ำเพียงฝั่งเดียวของตัวหมุน
3. CQuickselect ทำงานใน O(n) คาดหมาย และ median-of-medians รับประกัน O(n) ในกรณีเลวร้ายที่สุด
4. Dการเลือกต้องใช้ Ω(n log n) เสมอเพราะต้องเรียงลำดับ

ปัญหาความสอดคล้องข้อใดต่อไปนี้ทราบว่าแก้ได้ในเวลาพหุนาม

1. Aความสอดคล้องของวงจร
2. BSAT ทั่วไปบนสูตรรูปแบบนอร์มัลเชิงเชื่อม
3. C2-SAT ซึ่งแต่ละวลีมีลิเทอรัลไม่เกินสองตัว
4. D3-SAT ซึ่งแต่ละวลีมีลิเทอรัลสามตัวพอดี