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

เวลาทำงานของอัลกอริทึมเป็น O(n) การเติบโตแบบนี้เรียกว่าอะไร

1. Aลอการิทึม
2. Bกำลังสอง
3. Cเชิงเส้น
4. Dคงที่

อัลกอริทึมกำลังเดรัจฉาน (brute force) คืออะไร

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

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

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

การเรียกซ้ำของ merge sort สำหรับอาร์เรย์ n สมาชิกมีกี่ระดับ

1. Aประมาณ log₂ n
2. Bประมาณ n / 2
3. Cประมาณ n
4. Dประมาณ √n

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

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

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

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

Insertion sort ทำงานใน O(n) บนอินพุตที่เรียงแล้ว สิ่งนี้ขัดกับขอบเขตล่าง Ω(n log n) ของการเรียงแบบเปรียบเทียบหรือไม่

1. Aขัด ดังนั้นขอบเขตล่างจึงผิด
2. Bไม่ขัด ขอบเขตล่างใช้กับกรณีเลวร้ายที่สุดเหนือทุกอินพุต ไม่ใช่ทุกอินพุต
3. Cไม่ขัด เพราะ insertion sort ไม่ใช่การเรียงแบบเปรียบเทียบ
4. Dขัด แต่เฉพาะอาร์เรย์ที่สั้นกว่า 100

ข้อใดเกี่ยวกับสัญกรณ์ little-o ถูกต้อง

1. An² = o(n)
2. Bn = o(n²) แต่ n ไม่ใช่ o(n)
3. C2n = o(n) เพราะ 2n เติบโตช้า
4. Dn = o(n) เพราะทุกฟังก์ชันเป็น little-o ของตัวมันเอง