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

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

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

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

1. ALittle omega
2. BBig Theta
3. CBig O
4. DBig Omega

merge sort ใช้กลยุทธ์การออกแบบใด

1. Aการโปรแกรมพลวัต
2. Bการเลือกแบบละโมบ
3. Cกำลังเดรัจฉาน (brute force)
4. Dแบ่งแล้วเอาชนะ (divide and conquer)

การค้นหาแบบทวิภาคต้องเปรียบเทียบประมาณกี่ครั้งในกรณีเลวร้ายที่สุดบนอาร์เรย์ที่เรียงแล้วซึ่งมี 1,000,000 สมาชิก

1. Aประมาณ 20
2. Bประมาณ 500,000
3. Cประมาณ 1,000
4. Dประมาณ 100

ฟังก์ชันหนึ่งรันลูป n รอบ แล้วรันอีกลูป n รอบแยกต่างหาก ความซับซ้อนเชิงเวลาของมันคือเท่าใด

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

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

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

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

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

ความซับซ้อนเชิงเวลาของ for i = 1 to n: for (j = i; j ≤ n; j = j + i) ทำงาน O(1) คือเท่าใด

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