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

ความซับซ้อนเชิงเวลาของการค้นหาเชิงเส้นในอาร์เรย์ที่ไม่เรียงลำดับซึ่งมี n สมาชิก (กรณีเลวร้ายที่สุด) คือเท่าใด

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

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

1. A9 วินาที
2. B6 วินาที
3. C3 วินาที
4. D12 วินาที

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

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

อัลกอริทึมละโมบ (greedy) คือ

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

ความสัมพันธ์เวียนเกิด T(n) = T(n/2) + O(1) มีผลเฉลยเป็นเท่าใด

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

ฟังก์ชันแฟกทอเรียลแบบเรียกซ้ำง่าย ๆ fact(n) = n × fact(n − 1) ใช้พื้นที่สแต็กเท่าใด

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

เส้นทางง่ายที่สั้นที่สุดหาได้ในเวลาพหุนาม สิ่งใดที่ทราบเกี่ยวกับการหาเส้นทางง่ายที่ยาวที่สุดระหว่างสองจุดยอดในกราฟทั่วไป

1. Aเป็น NP-hard
2. Bตัดสินไม่ได้
3. Cแก้ได้ด้วยอัลกอริทึมของ Dijkstra โดยกลับเครื่องหมายน้ำหนัก
4. Dแก้ได้ใน O(V + E) เสมอ

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

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