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

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

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

อัลกอริทึม O(n) ใช้เวลา 3 วินาทีเมื่อ n = 1 ล้าน เมื่อ n = 2 ล้านจะใช้เวลาประมาณเท่าใด

1. A12 วินาที
2. B3 วินาที
3. C6 วินาที
4. D9 วินาที

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

1. Ao (little o)
2. BO (Big O)
3. CΩ (Big Omega)
4. DΘ (Big Theta)

คุณเรียงอาร์เรย์ n สมาชิกหนึ่งครั้ง แล้วตอบคำถามการเป็นสมาชิก k ข้อด้วยการค้นหาแบบทวิภาค ต้นทุนรวมเท่าใด

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

การวิเคราะห์แบบกระจายต้นทุน (amortised analysis) วัดสิ่งใด

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

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

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

เทคนิคใดให้เวลาทำงานคาดหมาย O(n log n) ของ quicksort กับอินพุตใด ๆ

1. Aเลือกสมาชิกตัวแรกเสมอ
2. Bเลือกตัวหลักแบบสุ่มสม่ำเสมอ
3. Cเรียงอินพุตก่อนรัน quicksort
4. Dเรียกซ้ำเฉพาะฝั่งซ้าย

การคำนวณจำนวนฟีโบนักชีตัวที่ n ด้วยลูปที่เก็บเพียงสองค่าล่าสุดมีต้นทุนด้านเวลาและพื้นที่เท่าใด

1. Aเวลา O(n) และพื้นที่ O(n)
2. Bเวลา O(2ⁿ) และพื้นที่ O(1)
3. Cเวลา O(log n) และพื้นที่ O(n)
4. Dเวลา O(n) และพื้นที่ O(1)