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

log₂ 1024 มีค่าเท่าใด

1. A10
2. B32
3. C12
4. D512

ความซับซ้อนเชิงเวลาในกรณีดีที่สุดของ insertion sort บนอาร์เรย์ที่เรียงแล้วคือเท่าใด

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

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

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

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

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

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

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

เหตุใดรูทีนการเรียงลำดับในไลบรารีจำนวนมากจึงเปลี่ยนไปใช้ insertion sort กับอาร์เรย์ย่อยที่เล็กมาก

1. AInsertion sort มีภาระเพิ่มน้อยและเร็วกับอินพุตที่เล็กหรือเกือบเรียงแล้ว
2. BInsertion sort เป็น O(n log n) ในกรณีเลวร้ายที่สุด
3. Cอัลกอริทึมแบบเรียกซ้ำจัดการอาร์เรย์ที่เล็กกว่า 10 สมาชิกไม่ได้
4. DInsertion sort ใช้หน่วยความจำน้อยกว่าอัลกอริทึมการเรียงลำดับอื่นทุกตัวกับอินพุตใหญ่

การคูณแบบ Karatsuba ตรงตาม T(n) = 3T(n/2) + O(n) ผลเฉลยคืออะไร

1. AΘ(n²)
2. BΘ(n³)
3. CΘ(n^{log₂ 3}) ประมาณ n^1.585
4. DΘ(n log n)

ความซับซ้อนเชิงเวลาของการสร้างฮีปไบนารีจากสมาชิก n ตัวที่ไม่เรียงลำดับด้วยวิธีล่างขึ้นบนคือเท่าใด

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